「题解」「POI2014」卡片 Card

(未完待续)

一道卡常数的 线段树 题目。

题目链接:Luogu P3569/LibreOJ 2466/POI2014 S2D0

题目

题目描述

桌面上有依次排列的 $n$ 张卡片,每张卡片有正反两面。共 $m$ 次操作,每次操作会交换两张卡片,询问交换后是否有可能通过改变卡片的正反来使卡片上的数不降。

数据范围

$$2\leq n\leq 2\times 10^5$$

$$1\leq m\leq 10^6$$

时空限制

题目时间限制空间限制
Luogu P3569$$1\text{s}$$$$62.5\text{MiB}$$
LibreOJ 2466$$1\text{s}$$$$64\text{MiB}$$
POI2014 S2D0$$1\text{s}$$$$64\text{MiB}$$

题解

思路

线段树维护即可,类似 「题解」迷宫 maze

代码

记得卡常数。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=200000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,m;
int a[MAXN][2];

inline void Read(void){
    n=read();
    for(reg int i=1;i<=n;++i)
        a[i][0]=read(),a[i][1]=read();
    return;
}

struct SegmentTree{
    #define lson ( (k) << 1 )
    #define rson ( (k) << 1 | 1 )
    #define mid ( ( (l) + (r) ) >> 1 )
    bool unit[MAXN<<2][2][2];
    inline void pushup(reg int k,reg int l,reg int r){
        unit[k][0][0]=unit[k][0][1]=unit[k][1][0]=unit[k][1][1]=false;
        if(r-l>1)
            for(reg int i=0,j;i<2;++i)
                for(j=0;j<2;++j){
                    if(a[mid][0]<=a[mid+1][0])
                        unit[k][i][j]|=unit[lson][i][0]&&unit[rson][0][j];
                    if(a[mid][0]<=a[mid+1][1])
                        unit[k][i][j]|=unit[lson][i][0]&&unit[rson][1][j];
                    if(a[mid][1]<=a[mid+1][0])
                        unit[k][i][j]|=unit[lson][i][1]&&unit[rson][0][j];
                    if(a[mid][1]<=a[mid+1][1])
                        unit[k][i][j]|=unit[lson][i][1]&&unit[rson][1][j];
                }
        else{
            unit[k][0][0]=a[mid][0]<=a[mid+1][0];
            unit[k][0][1]=a[mid][0]<=a[mid+1][1];
            unit[k][1][0]=a[mid][1]<=a[mid+1][0];
            unit[k][1][1]=a[mid][1]<=a[mid+1][1];
        }
        return;
    }

    inline void Build(reg int k,reg int l,reg int r){
        if(l==r){
            unit[k][0][0]=true;
            unit[k][1][1]=true;
            unit[k][0][1]=a[l][0]<=a[l][1];
            unit[k][1][0]=a[l][1]<=a[l][0];
            return;
        }
        Build(lson,l,mid);
        Build(rson,mid+1,r);
        pushup(k,l,r);
        return;
    }
    inline void Update(reg int k,reg int l,reg int r,reg int pos){
        if(l==r&&l==pos){
            unit[k][0][0]=true;
            unit[k][1][1]=true;
            unit[k][0][1]=a[l][0]<=a[l][1];
            unit[k][1][0]=a[l][1]<=a[l][0];
            return;
        }
        if(pos<=mid)
            Update(lson,l,mid,pos);
        if(pos>mid)
            Update(rson,mid+1,r,pos);
        pushup(k,l,r);
        return;
    }
    inline bool Query(reg int k){
        reg bool res=false;
        for(reg int i=0,j;i<2;++i)
            for(j=0;j<2;++j)
                res|=unit[k][i][j];
        return res;
    }
    #undef lson
    #undef rson
    #undef mid
};

SegmentTree T;

inline void Work(void){
    T.Build(1,1,n);
    m=read();
    while(m--){
        static int u,v;
        u=read(),v=read();
        swap(a[u][0],a[v][0]);
        swap(a[u][1],a[v][1]);
        T.Update(1,1,n,u);
        T.Update(1,1,n,v);
        puts(T.Query(1)?"TAK":"NIE");
    }
    return;
}