bzoj 3526: [Poi2014]Card 線段樹

NO IMAGE

題意

有n張卡片在桌上一字排開,每張卡片上有兩個數,第i張卡片上,正面的數為a[i],反面的數為b[i]。現在,有m個熊孩子來破壞你的卡片了!
第i個熊孩子會交換c[i]和d[i]兩個位置上的卡片。
每個熊孩子搗亂後,你都需要判斷,通過任意翻轉卡片(把正面變為反面或把反面變成正面,但不能改變卡片的位置),能否讓卡片正面上的數從左到右單調不降。
n≤200000,m≤1000000,0≤a[i],b[i]≤10000000,1≤c[i],d[i]≤n.

分析

一開始想到線段樹每個端點維護一個大小為4的布林陣列表示左端點個右端點取某個值時是否存在可行方案,然後合併的時候要乘上一個16倍的大常數,交一下果然T了。
但看到網上有人跟我用一樣的方法過了,突然想起下午看到ImmortalCO在知乎上發了一篇文章,說寫ds時直接開陣列會比開struct快上一些,然後就改成了直接開陣列,成功在bzoj上卡時通過。
然後在網上看到一個做法,就是說對每個節點開一個大小為2的int陣列表示左端點取某個值時最小的右端點是多少,若不存在合法方案則為inf。這樣的話常數可以除掉4,於是成功跑進第三榜。

程式碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ls d<<1
#define rs d<<1|1
const int N=200005;
const int inf=1000000000;
int n,m,a[N][2],w[N*4][2];
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10 ch-'0';ch=getchar();}
return x*f;
}
void updata(int d,int l,int r)
{
int mid=(l r)/2;
w[d][0]=w[d][1]=inf;
if (w[ls][0]<=a[mid 1][0]) w[d][0]=std::min(w[d][0],w[rs][0]);
if (w[ls][0]<=a[mid 1][1]) w[d][0]=std::min(w[d][0],w[rs][1]);
if (w[ls][1]<=a[mid 1][0]) w[d][1]=std::min(w[d][1],w[rs][0]);
if (w[ls][1]<=a[mid 1][1]) w[d][1]=std::min(w[d][1],w[rs][1]);
}
void build(int d,int l,int r)
{
if (l==r) {w[d][0]=a[l][0];w[d][1]=a[l][1];return;}
int mid=(l r)/2;
build(ls,l,mid);build(rs,mid 1,r);
updata(d,l,r);
}
void modify(int d,int l,int r,int x)
{
if (l==r) {w[d][0]=a[x][0];w[d][1]=a[x][1];return;}
int mid=(l r)/2;
if (x<=mid) modify(ls,l,mid,x);
else modify(rs,mid 1,r,x);
updata(d,l,r);
}
int main()
{
n=read();
for (int i=1;i<=n;i  ) a[i][0]=read(),a[i][1]=read();
build(1,1,n);
m=read();
while (m--)
{
int x=read(),y=read();
std::swap(a[x][0],a[y][0]);
std::swap(a[x][1],a[y][1]);
modify(1,1,n,x);
modify(1,1,n,y);
if (w[1][0]<inf||w[1][1]<inf) puts("TAK");
else puts("NIE");
}
return 0;
}