二分 + 并查集

题目链接：https://www.luogu.org/problemnew/show/2898

题目大意：

给一段长度为n，每个位置上的数都不同的序列a[1..n]和q和问答， 每个问答是(x, y, r)代表RMQ(a, x, y) = r, 要你给出最早的有矛盾的那个问答的编号。

 

首先，要你求的是出现矛盾的，那什么时候才会出现矛盾呢？

可以总结为两种情况：

①之前已更新这个区间最小值为x，又要更新此区间的子区间（或这个区间）的最小值为更小的数。

这样~

（黑色是已更新区间，红色是这次操作的区间。）

②两段区间的最小值相同，但没有交集。

（因为题目中说数字互不相同，所以不可能一个数字同时出现在两个位置~QAQ）

就是这样子~

但是注意合并的时候要合并到r + 1,为了防止这种情况：

③已知[1,2] Min = 2 , [3,4] Min = 4,现在要合并一段区间[1,4] Min = 1,

很明显是矛盾的，但是如果把fa合并到r不会判出矛盾。

 

怎么判是不是有交集和是不是完全被包含呢？

有没有发现我在反复用一个词：集合！！

集合操作什么的当然是并查集！

那怎么找到矛盾的操作呢？

二分！（10^6）

 

为了容易判断情况二，先让Min从大到小排个序。

判断情况一：

if(t[i].Min < t[i - 1].Min){     if(find(lmax) > rmin) //满足情况一         return true;     for(int j = lmin;j <= rmax;++ j) //合并上一个区间 　　　　　fa[find[j] = find(rmax + 1);//都合并到rmax + 1，为了防止情况③     lmax = lmin = t[i].l;//更新成这个区间的l,r     rmax = rmin = t[i].r;}

其实合并的时候，每次都找一遍find(j)相当于把已经合并过的集合又每个点都扫了一遍，

但是已经合并过其实可以直接跳到find(j),

就是这样：

for(int j = lmin;j <= rmax;++ j){                j = find(j);                fa[j] = find(rmax + 1);}

这里是1s和2s的区别

 

判断情况二：

else if(t[i].Min == t[i - 1].Min){            lmax = max(lmax,t[i].l);            lmin = min(lmin,t[i].l);            rmax = max(rmax,t[i].r);            rmin = min(rmin,t[i].r);            if(lmax > rmin)//看图理解                return true;}

整个Check就是这样的：

bool check(int k){//前k句话是否出现过矛盾    for(int i = 1;i <= n + 1;++ i) fa[i] = i;    for(int i = 1;i <= k;++ i) t[i] = a[i];    int lmin,lmax,rmin,rmax;    sort(t + 1,t + 1 + k,cmp);//为了好判断情况二，先把 Min sort一遍    lmax = lmin = t[1].l;    rmin = rmax = t[1].r;    for(int i = 2;i <= k;++ i){        if(t[i].Min < t[i - 1].Min){//情况二            if(find(lmax) > rmin)                return true;            for(int j = lmin;j <= rmax;++ j){                j = find(j);                fa[j] = find(rmax + 1);                //fa[find(j)] = find(rmax + 1);            }            lmax = lmin = t[i].l;            rmax = rmin = t[i].r;        }        else {//情况一            lmax = max(lmax,t[i].l);            lmin = min(lmin,t[i].l);            rmax = max(rmax,t[i].r);            rmin = min(rmin,t[i].r);            if(lmax > rmin)                return true;        }    }    if(find(lmax) > rmin)        return true;    return false;}

 for到k就可以了，因为在出来while的时候又判了一遍。

还有注意定义全局变量QAQQQQQ

这个题就是这样了~

 Codes:

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N = 1000000 + 10;int n,ans,q;int fa[N];struct node{    int l,r,Min;}t[N],a[N];inline int read(){    int x = 0, f = 1;    char ch = getchar();    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;    for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';    return x * f;}bool cmp(node x,node y){    return x.Min > y.Min;}int find(int x){    if(x == fa[x]) return x;    return fa[x] = find(fa[x]);}bool check(int k){    for(int i = 1;i <= n + 1;++ i) fa[i] = i;    for(int i = 1;i <= k;++ i) t[i] = a[i];    int lmin,lmax,rmin,rmax;    sort(t + 1,t + 1 + k,cmp);    lmax = lmin = t[1].l;    rmin = rmax = t[1].r;    for(int i = 2;i <= k;++ i){        if(t[i].Min < t[i - 1].Min){            if(find(lmax) > rmin)                return true;            for(int j = lmin;j <= rmax;++ j){                j = find(j);                fa[j] = find(rmax + 1);                //fa[find(j)] = find(rmax + 1);            }            lmax = lmin = t[i].l;            rmax = rmin = t[i].r;        }        else if(t[i].Min == t[i - 1].Min){            lmax = max(lmax,t[i].l);            lmin = min(lmin,t[i].l);            rmax = max(rmax,t[i].r);            rmin = min(rmin,t[i].r);            if(lmax > rmin)                return true;        }    }    if(find(lmax) > rmin)        return true;    return false;}int main(){    n = read();    q = read();    for(int i = 1;i <= q;++ i)        a[i].l = read(),        a[i].r = read(),        a[i].Min = read();    int l = 1,r = q ;    ans = 0;    while(r - l > 1){        int mid = (l + r) >> 1;        if(check(mid))            ans = mid,            r = mid;        else             l = mid;    }    cout << ans << '\n';    return 0;}
        
       
      
     

 

MAS:

集合操作注意并查集。

定义全局变量！！