P3569 [POI2014] KAR-Cards 题解

· · 题解

题目大意

给你 n 个二元组序列 (a_i,b_i)，接下来会进行 m 次操作，每次交换一对二元组，每次交换后请你判断，是否能从每个二元组中选择一个数，按顺序构成单调不增的序列。

题目分析

线段树板中板。

假如是一个普通的序列，我们可以建一颗线段树，只要左区间合法，右区间合法，并且左区间的右端点小于等于右区间的左端点，则当前区间也合法。交换则是两个单点修改。

那这只是多了个元，那就记录左右端点分别取某个值时是否合法，再判两个端点的大小关系就行了。复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define ll long long
#define L x<<1
#define R x<<1|1
#define mid (l+r>>1LL)
#define lc L,l,mid
#define rc R,mid+1,r
#define Root 1,1,n
#define OK l>=Ll&&r<=Rr
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define pb push_back
#define ull unsigned ll
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
#define Pi pair<int,int>
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57) s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(ll x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
const int N =2e5+5,M=1e6+5;
const ll llf=1e18,mod=998244353,bas=131;
const ui base=13331;
using namespace std;
int n=read(),m,a[N],b[N];
struct seg{
    bool f11,f12,f21,f22;
    int l1,l2,r1,r2;
}xd[N<<2];
inline seg getup(seg a,seg b){
    seg c;
    c={0,0,0,0,a.l1,a.l2,b.r1,b.r2};
    if(a.r1<=b.l1)c.f11|=a.f11&b.f11,c.f12|=a.f11&b.f12,c.f21|=a.f21&b.f11,c.f22|=a.f21&b.f12;
    if(a.r2<=b.l1)c.f11|=a.f12&b.f11,c.f12|=a.f12&b.f12,c.f21|=a.f22&b.f11,c.f22|=a.f22&b.f12;
    if(a.r1<=b.l2)c.f11|=a.f11&b.f21,c.f12|=a.f11&b.f22,c.f21|=a.f21&b.f21,c.f22|=a.f21&b.f22;
    if(a.r2<=b.l2)c.f11|=a.f12&b.f21,c.f12|=a.f12&b.f22,c.f21|=a.f22&b.f21,c.f22|=a.f22&b.f22;
    return c;
}
inline void build(int x,int l,int r){
    if(l==r){
        xd[x]={1,1,0,1,a[l],b[l],a[l],b[l]};
        if(a[l]==b[l])xd[x].f21=1;
        return;
    }
    build(lc),build(rc),xd[x]=getup(xd[L],xd[R]);
}
inline void modify(int x,int l,int r,int p){
    if(l==r){
        xd[x]={1,1,0,1,a[l],b[l],a[l],b[l]};
        if(a[l]==b[l])xd[x].f21=1;
        return;
    }
    if(p<=mid)modify(lc,p);
    else modify(rc,p);
    xd[x]=getup(xd[L],xd[R]);
}
int main(){
    rep(i,1,n){
        a[i]=read(),b[i]=read();
        if(a[i]>b[i])swap(a[i],b[i]);
    }
    build(Root);
    m=read();
    for(int i=1,x,y;i<=m;i++){
        x=read(),y=read();
        swap(a[x],a[y]),swap(b[x],b[y]);
        modify(Root,x),modify(Root,y);
        //cout <<xd[1].l1<<xd[1].l2<<xd[1].r1<<xd[1].r2<<'\n';
        printf("%s\n",(xd[1].f11|xd[1].f12|xd[1].f21|xd[1].f22)?"TAK":"NIE");
    }

    return 0;
}