CodeForces gym Nasta Rabbara lct

Nasta Rabbara

题意：简单来说就是，现在有 n个点， m条边，每次询问一个区间[ l , r ]，将这个区间的所有边都连上，如果现在的图中有奇数环，就输出 “Impossible”，否者就输出 ”possible“。

题解：

步骤1：我们先找出每个最小的 [ l, r] 当这个区间的边都出现后，就会出现一个奇数环。

步骤2：问题就变成了对于一次询问 [ L, R ] 是否存在上面的一个区间被完全覆盖。

对于步骤1来说：需要加边和删边，我们用 lct 维护。

我们按照 1 ... m 的顺序，进行添加边。

如果 u 和 v 不联通，那么我们直接将u和v连起来。

如果 u 和 v 联通，那么如果我们加上这个边之后就会形成环。

如果是偶数环，那么我们就删除这个环上最先添加进来的边，因为我们需要找到最小的[l, r]奇数环区间。

如果是奇数环，那么说明我们已经找到了一个奇数环区间，因为有偶数环删除的保证，所以我们找到的一定是最小的奇数环区间。

然后我们再删除边，将 l+1前面的边都删除，继续往下找下一个最小奇数环区间。

对于步骤2来说：

我们可以离线所有询问。

对于所有的最小奇数环区间和询问区间都按照左端点大的排序。

当询问区间的左端点的位置 <= 当前奇数环区间的时候，就在标记一下奇数环区间的右端，用树状数组维护。

然后查询询问区间的右端点之前有没有点出现过，如果有就说明有区间被完全覆盖。

因为添加到树状数组里面的奇数环区间的左端点一定是大或等于当前区间左端点的。

最后输出答案。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("2.in","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define lch(x) tr[x].son[0]

 #define rch(x) tr[x].son[1]

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 2e5 + ;

 struct Node{

     int rev, rt;

     int son[], pre;

     int id, mn, sz;

     void init(int t){

         sz = rt = ;

         rev = pre = son[] = son[] = ;

         id = mn = t;

     }

 }tr[N];

 void Push_Rev(int x){

     if(!x) return ;

     swap(lch(x), rch(x));

     tr[x].rev ^= ;

 }

 void Push_Up(int x){

     if(!x) return ;

     tr[x].sz = tr[lch(x)].sz + tr[rch(x)].sz + ;

     tr[x].mn = min3(tr[lch(x)].mn, tr[rch(x)].mn, tr[x].id);

 }

 void Push_Down(int x){

    if(tr[x].rev){

         tr[x].rev = ;

         Push_Rev(lch(x));

         Push_Rev(rch(x));

     }

 }

 void Rev(int x){

     if(!tr[x].rt) Rev(tr[x].pre);

     Push_Down(x);

 }

 void rotate(int x){

     if(tr[x].rt) return;

     int y = tr[x].pre, z = tr[y].pre;

     int k = (rch(y) == x);

     tr[y].son[k] = tr[x].son[k^];

     tr[tr[y].son[k]].pre = y;

     tr[x].son[k^] = y;

     tr[y].pre = x;

     tr[x].pre = z;

     if(tr[y].rt) tr[y].rt = , tr[x].rt = ;

     else tr[z].son[rch(z) == y] = x;

     Push_Up(y);

 }

 void Splay(int x){

      Rev(x);

      while(!tr[x].rt){

         int y = tr[x].pre, z = tr[y].pre;

         if(!tr[y].rt){

             if(( x == rch(y) ) != (y == rch(z))) rotate(y);

             else rotate(x);

         }

         rotate(x);

     }

     Push_Up(x);

 }

 void Access(int x){

     int y = ;

     do{

         Splay(x);

         tr[rch(x)].rt = ;

         rch(x) = y;

         tr[y].rt = ;

         Push_Up(x);

         y = x;

         x = tr[x].pre;

     }while(x);

 }

 void Make_rt(int x){

     Access(x);

     Splay(x);

     Push_Rev(x);

 }

 void link(int u, int v){

     Make_rt(u);

     tr[u].pre = v;

 }

 void cut(int u, int v){

     Make_rt(u);

     Access(v);

     Splay(v);

     tr[lch(v)].pre = ;

     tr[lch(v)].rt = ;

     tr[v].pre = ;

     lch(v) = ;

 }

 bool judge(int u, int v){

     while(tr[u].pre) u = tr[u].pre;

     while(tr[v].pre) v = tr[v].pre;

     return u == v;

 }

 int x[N], y[N];

 int l[N], r[N];

 int in[N];

 int ans[N];

 int tot = ;

 int n, m, q;

 struct node{

     int l, r, id;

     bool operator < (const node & x) const {

         return l > x.l;

     }

 }A[N];

 void solve(int st, int ed){

     for(int i = st; i <= ed; i++){

         if(!in[i]) continue;

         cut(x[i], i+n);

         cut(y[i], i+n);

         in[i] = ;

     }

 }

 int tree[N];

 inline int lowbit(int x){

     return x & (-x);

 }

 int Query(int x){

     int ret = ;

     while(x){

         ret += tree[x];

         x -= lowbit(x);

     }

     return ret;

 }

 void Add(int x){

     while(x <= m){

         tree[x]++;

         x += lowbit(x);

     }

 }

 int main(){

     scanf("%d%d%d", &n, &m, &q);

     for(int i = ; i <= n; i++) tr[i].init(inf);

     tr[].mn = tr[].id = inf;

     for(int i = ; i <= m; i++){

         scanf("%d%d", &x[i], &y[i]);

         tr[i+n].init(i+n);

     }

     int b = ;

     for(int i = ; i <= m; i++){

         int u = x[i], v = y[i], id = n+i;

         if(!judge(u, v)){

             link(u, id);

             link(v, id);

             in[i] = ;

         }

         else {

             Make_rt(u);

             Access(v);

             Splay(v);

             int sz = tr[v].sz/;

             int t = tr[v].mn;

             if(sz&) {

                 cut(u, t);

                 cut(v, t);

                 in[t-n] = ;

             }

             else {

                 l[++tot] = t-n; r[tot] = i;

                 solve(b, t-n);

                 b = t-n;

             }

             link(u, id);

             link(v, id);

             in[i] = ;

         }

     }

     for(int i = ; i <= q; i++){

         scanf("%d%d", &A[i].l, &A[i].r);

         A[i].id = i;

     }

     sort(A+, A++q);

     for(int i = ; i <= q; i++){

         int ll = A[i].l, rr = A[i].r, id = A[i].id;

         while(tot && ll <= l[tot]){

             Add(r[tot]);

             tot--;

         }

         if(Query(rr)) ans[id] = ;

     }

     for(int i = ; i <= q; i++){

         if(ans[i]) puts("Impossible");

         else puts("Possible");

     }

     return ;

 }

因为一直在实验室问步骤2的问题，又听到一个别的思路。

因为我们保证了最小奇数环区间是没有覆盖情况的，我们按照左端点小的排序。

对于每次询问我们找到第一段左端点大于询问区间的左端点的区间，然后判断一下右端点是不是在这个区间里面就好了。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("2.in","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define lch(x) tr[x].son[0]

 #define rch(x) tr[x].son[1]

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 2e5 + ;

 struct Node{

     int rev, rt;

     int son[], pre;

     int id, mn, sz;

     void init(int t){

         sz = rt = ;

         rev = pre = son[] = son[] = ;

         id = mn = t;

     }

 }tr[N];

 void Push_Rev(int x){

     if(!x) return ;

     swap(lch(x), rch(x));

     tr[x].rev ^= ;

 }

 void Push_Up(int x){

     if(!x) return ;

     tr[x].sz = tr[lch(x)].sz + tr[rch(x)].sz + ;

     tr[x].mn = min3(tr[lch(x)].mn, tr[rch(x)].mn, tr[x].id);

 }

 void Push_Down(int x){

    if(tr[x].rev){

         tr[x].rev = ;

         Push_Rev(lch(x));

         Push_Rev(rch(x));

     }

 }

 void Rev(int x){

     if(!tr[x].rt) Rev(tr[x].pre);

     Push_Down(x);

 }

 void rotate(int x){

     if(tr[x].rt) return;

     int y = tr[x].pre, z = tr[y].pre;

     int k = (rch(y) == x);

     tr[y].son[k] = tr[x].son[k^];

     tr[tr[y].son[k]].pre = y;

     tr[x].son[k^] = y;

     tr[y].pre = x;

     tr[x].pre = z;

     if(tr[y].rt) tr[y].rt = , tr[x].rt = ;

     else tr[z].son[rch(z) == y] = x;

     Push_Up(y);

 }

 void Splay(int x){

      Rev(x);

      while(!tr[x].rt){

         int y = tr[x].pre, z = tr[y].pre;

         if(!tr[y].rt){

             if(( x == rch(y) ) != (y == rch(z))) rotate(y);

             else rotate(x);

         }

         rotate(x);

     }

     Push_Up(x);

 }

 void Access(int x){

     int y = ;

     do{

         Splay(x);

         tr[rch(x)].rt = ;

         rch(x) = y;

         tr[y].rt = ;

         Push_Up(x);

         y = x;

         x = tr[x].pre;

     }while(x);

 }

 void Make_rt(int x){

     Access(x);

     Splay(x);

     Push_Rev(x);

 }

 void link(int u, int v){

     Make_rt(u);

     tr[u].pre = v;

 }

 void cut(int u, int v){

     Make_rt(u);

     Access(v);

     Splay(v);

     tr[lch(v)].pre = ;

     tr[lch(v)].rt = ;

     tr[v].pre = ;

     lch(v) = ;

 }

 bool judge(int u, int v){

     while(tr[u].pre) u = tr[u].pre;

     while(tr[v].pre) v = tr[v].pre;

     return u == v;

 }

 int x[N], y[N];

 int in[N];

 int ans[N];

 int tot = ;

 pll P[N];

 int n, m, q;

 void solve(int st, int ed){

     for(int i = st; i <= ed; i++){

         if(!in[i]) continue;

         cut(x[i], i+n);

         cut(y[i], i+n);

         in[i] = ;

     }

 }

 int main(){

     scanf("%d%d%d", &n, &m, &q);

     for(int i = ; i <= n; i++) tr[i].init(inf);

     tr[].mn = tr[].id = inf;

     for(int i = ; i <= m; i++){

         scanf("%d%d", &x[i], &y[i]);

         tr[i+n].init(i+n);

     }

     int b = ;

     for(int i = ; i <= m; i++){

         int u = x[i], v = y[i], id = n+i;

         if(!judge(u, v)){

             link(u, id);

             link(v, id);

             in[i] = ;

         }

         else {

             Make_rt(u);

             Access(v);

             Splay(v);

             int sz = tr[v].sz/;

             int t = tr[v].mn;

             if(sz&) {

                 cut(u, t);

                 cut(v, t);

                 in[t-n] = ;

             }

             else {

                 P[tot].fi = t-n; P[tot++].se = i;

                 solve(b, t-n);

                 b = t-n;

             }

             link(u, id);

             link(v, id);

             in[i] = ;

         }

     }

     int l, r;

     for(int i = ; i <= q; i++){

         scanf("%d%d", &l, &r);

         int p = upper_bound(P, P+tot, pll(l,-)) - P;

         if(p == tot || r < P[p].se) puts("Possible");

         else puts("Impossible");

     }

     return ;

 }

巴特西

CodeForces gym Nasta Rabbara lct

最新文章

热门文章