BZOJ 3526: [Poi2014]Card

3526: [Poi2014]Card

Time Limit: 25 Sec Memory Limit: 64 MB
Submit: 267 Solved: 191
[Submit][Status][Discuss]

Description

有n张卡片在桌上一字排开，每张卡片上有两个数，第i张卡片上，正面的数为a[i]，反面的数为b[i]。现在，有m个熊孩子来破坏你的卡片了！
第i个熊孩子会交换c[i]和d[i]两个位置上的卡片。
每个熊孩子捣乱后，你都需要判断，通过任意翻转卡片（把正面变为反面或把反面变成正面，但不能改变卡片的位置），能否让卡片正面上的数从左到右单调不降。

Input

第一行一个n。
接下来n行，每行两个数a[i],b[i]。
接下来一行一个m。
接下来m行，每行两个数c[i],d[i]。

Output

m行，每行对应一个答案。如果能成功，输出TAK，否则输出NIE。

Sample Input

4
2 5
3 4
6 3
2 7
2
3 4
1 3

Sample Output

NIE
TAK

HINT

【样例解释】

交换3和4后，卡片序列为(2,5) (3,4) (2,7) (6,3)，不能成功。

交换1和3后，卡片序列为(2,7) (3,4) (2,5) (6,3)，翻转第3张卡片，卡片的正面为2,3,5,6，可以成功。

【数据范围】

n≤200000，m≤1000000，0≤a[i],b[i]≤10000000,1≤c[i],d[i]≤n.

Source

By Dzy

[Submit][Status][Discuss]

好有趣的一道题，老早就写过，现在又重新写一遍，强行缩代码，2333.

就是用线段树，维护每个区间，如果选取区间左端较小值，右端能以什么结尾；如果选取区间左端较大值，右端能以什么结尾。

 #include<cstdio>

 #define mxn 200005

 #define siz 800005

 #define mxm 1000005

 #define swap(a,b) a^=b^=a^=b

 int n,m,a[mxn],b[mxn],c,d,A[siz],B[siz];

 void update(int t,int l,int r,int d,int ls,int rs){

     A[t]=B[t]=;

     if((A[ls]==&&a[d]<=b[d+])||(A[ls]==&&b[d]<=b[d+]))A[t]=B[rs];

     if((A[ls]==&&a[d]<=a[d+])||(A[ls]==&&b[d]<=a[d+]))A[t]=A[rs];

     if((B[ls]==&&a[d]<=b[d+])||(B[ls]==&&b[d]<=b[d+]))B[t]=B[rs];

     if((B[ls]==&&a[d]<=a[d+])||(B[ls]==&&b[d]<=a[d+]))B[t]=A[rs];

 }

 void build(int t,int l,int r){

     if(l==r){A[t]=;B[t]=;return;}

     int d=(l+r)>>,ls=t<<,rs=t<<|;

     build(ls,l,d),build(rs,d+,r);

     update(t,l,r,d,ls,rs);

 }

 void rebuild(int t,int l,int r,int p){

     if(l==r){A[t]=;B[t]=;return;}

     int d=(l+r)>>,ls=t<<,rs=t<<|;

     if(p<=d)rebuild(ls,l,d,p);else rebuild(rs,d+,r,p);

     update(t,l,r,d,ls,rs);

 }

 main(){

     scanf("%d",&n);

     for(int i=;i<=n;++i)scanf("%d%d",a+i,b+i);

     for(int i=;i<=n;++i)if(a[i]>b[i])swap(a[i],b[i]);

     build(,,n);

     scanf("%d",&m);

     for(int i=;i<=m;++i)scanf("%d%d",&c,&d),puts((swap(a[c],a[d]),swap(b[c],b[d]),rebuild(,,n,c),rebuild(,,n,d),A[])?"TAK":"NIE");

 }

原来的代码看起来好冗长的样子……

 #include <cmath>

 #include <cstdio>

 #include <string>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int N = ;

 const int M = ;

 int n, m;

 struct card

 {

     int a, b;

     card(void) {};

     card(int _a, int _b)

     {

         a = min(_a, _b);

         b = max(_a, _b);

     }

 }c[N];

 struct node

 {

     int lt, rt;

     int valA, valB;

 }tree[N << ];

 void buildTree(int p, int l, int r)

 {

     node &t = tree[p];

     t.lt = l, t.rt = r;

     if (t.lt == t.rt)

     {

         t.valA = ;

         t.valB = ;

         return;

     }

     int mid = (t.lt + t.rt) >> ;

     buildTree(p << , t.lt, mid);

     buildTree(p <<  | , mid + , t.rt);

     t.valA = t.valB = ;

     switch (tree[p << ].valA)

     {

         case :

             if (c[mid].a <= c[mid + ].b)

                 t.valA = tree[p <<  | ].valB;

             if (c[mid].a <= c[mid + ].a)

                 t.valA = tree[p <<  | ].valA;

             break;

         case :

             if (c[mid].b <= c[mid + ].b)

                 t.valA = tree[p <<  | ].valB;

             if (c[mid].b <= c[mid + ].a)

                 t.valA = tree[p <<  | ].valA;

             break;

     }

     switch (tree[p << ].valB)

     {

         case :

             if (c[mid].a <= c[mid + ].b)

                 t.valB = tree[p <<  | ].valB;

             if (c[mid].a <= c[mid + ].a)

                 t.valB = tree[p <<  | ].valA;

             break;

         case :

             if (c[mid].b <= c[mid + ].b)

                 t.valB = tree[p <<  | ].valB;

             if (c[mid].b <= c[mid + ].a)

                 t.valB = tree[p <<  | ].valA;

             break;

     }

 }

 void change(int p, int pos)

 {

     node &t = tree[p];

     if (t.lt == t.rt)

     {

         t.valA = ;

         t.valB = ;

         return;

     }

     int mid = (t.lt + t.rt) >> ;

     if (pos <= mid)

         change(p << , pos);

     else

         change(p <<  | , pos);

     t.valA = t.valB = ;

     switch (tree[p << ].valA)

     {

         case :

             if (c[mid].a <= c[mid + ].b)

                 t.valA = tree[p <<  | ].valB;

             if (c[mid].a <= c[mid + ].a)

                 t.valA = tree[p <<  | ].valA;

             break;

         case :

             if (c[mid].b <= c[mid + ].b)

                 t.valA = tree[p <<  | ].valB;

             if (c[mid].b <= c[mid + ].a)

                 t.valA = tree[p <<  | ].valA;

             break;

     }

     switch (tree[p << ].valB)

     {

         case :

             if (c[mid].a <= c[mid + ].b)

                 t.valB = tree[p <<  | ].valB;

             if (c[mid].a <= c[mid + ].a)

                 t.valB = tree[p <<  | ].valA;

             break;

         case :

             if (c[mid].b <= c[mid + ].b)

                 t.valB = tree[p <<  | ].valB;

             if (c[mid].b <= c[mid + ].a)

                 t.valB = tree[p <<  | ].valA;

             break;

     }

 }

 signed main(void)

 {

     scanf("%d", &n);

     for (int i = , a, b; i <= n; ++i)

         scanf("%d%d", &a, &b), c[i] = card(a, b);

     buildTree(, , n);

     scanf("%d", &m);

     for (int i = , a, b; i <= m; ++i)

     {

         scanf("%d%d", &a, &b);

         swap(c[a], c[b]);

         change(, a);

         change(, b);

         if (tree[].valA)

             puts("TAK");

         else

             puts("NIE");

     }

 }

@Author: YouSiki

巴特西