NKOJ 3777カード操作(セグメントツリー)

P 3777カード操作
問題の説明

    n          ，         ， i    ，     a[i]，     b[i]。  ， m            ！
    i       c[i] d[i]        。
           ，      ，        （               ，          ），                  。

入力フォーマット

     n。
   n ，     a[i],b[i]。
       m。
   m ，     c[i],d[i]。

出力フォーマット

m ，        。     ，  TAK，    NIE。

サンプル入力

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

サンプル出力

NIE
TAK

ヒント

【    】
  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.

まず図論の思想を使って、1つのカードを2つの点AiとBiと見なして、Ai<=Biを設けて、もしAiの値がAi+1より小さいならば、1本のAiからAi+1の辺を指して、同じようにすべての点を処理します.では,解があるかどうかの問題は,1からnまでの経路があるかどうかを問うことになる.
次に、セグメントツリーを使用して接続性を維持します.
ALからR番点に到達できるときの最小の重み値をVaで表し,VbはBLから出発する区間[L,R]について議論する.ではlsは区間の左息子,rsは右息子であり,左右の息子の値から[L,R]の値を算出できるかどうかを考える必要がある.midをL+R>>1とする.
まずVa[L,R]を算出することを考えると,Vals<=Amid+1であればmid点からAmid+1に接続できることを意味するので,Va[L,R]=Varsである.そうでなければVals<=Bmid+1を議論し,成立はmid点からBmid+1に接続できることを意味するので,Va[L,R]=Vbrsである.いずれも満たされない場合、midはmid+1に接続できず、ALからARまたはBRへの経路が存在しないことを意味し、Va[L,R]=infである.
Vb［L,R］同理計算.最後にVa[1,n]とVb[1,n]が存在するかどうかを見るだけでよい.
修正については明らかに単点修正です.具体的にはコードを参照できます.
コード:

#include
#include
#include
#define N 222222
#define M 2222222
using namespace std;
int n,A[N],B[N],m;
int ls[M],rs[M],va[M],vb[M],tot;
void UD(int p,int l,int r)
{
    int mid=(l+r>>1)+1;
    if(va[ls[p]]<=A[mid])va[p]=va[rs[p]];
    else if(va[ls[p]]<=B[mid])va[p]=vb[rs[p]];
    else va[p]=1e9;
    if(vb[ls[p]]<=A[mid])vb[p]=va[rs[p]];
    else if(vb[ls[p]]<=B[mid])vb[p]=vb[rs[p]];
    else vb[p]=1e9;
}
int BT(int x,int y)
{
    int p=++tot;
    if(xint mid=x+y>>1;
        ls[p]=BT(x,mid);
        rs[p]=BT(mid+1,y);
        UD(p,x,y);
    }
    else va[p]=A[x],vb[p]=B[x];
    return p;
}
void CHA(int p,int l,int r,int k)
{
    if(l==r){va[p]=A[l];vb[p]=B[l];return;}
    int mid=l+r>>1;
    if(k<=mid)CHA(ls[p],l,mid,k);
    else CHA(rs[p],mid+1,r,k);
    UD(p,l,r);
}
int main()
{
    int i,x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&A[i],&B[i]);
        if(A[i]>B[i])swap(A[i],B[i]);
    }
    BT(1,n);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        swap(A[x],A[y]);
        swap(B[x],B[y]);
        CHA(1,1,n,x);
        CHA(1,1,n,y);
        if(va[1]!=1e9||vb[1]!=1e9)puts("TAK");
        else puts("NIE");
    }
}