3526: [Poi2014]Card 线段树

题解：

考虑对于每个线段树节点记录如果第一个元素选择比较大的，那么最后一个元素最小是多少；选择比较小的同理。

如果不能选到节点的最后一个元素则值为$\infty$。

信息非常容易维护与合并。

交换操作相当于线段树的单点修改。

这样的话就在$O(mlogn)$之内解决了。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define inf 0x3f3f3f3f

inline int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
inline int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}

inline void mini(int&x,int y){
	if(x>y)
		x=y;
}
struct Ans{
	int mx[2],mn[2];
	inline void init(int x,int y){
		if(x>y)
			swap(x,y);
		mn[0]=mn[1]=x;
		mx[0]=mx[1]=y;
	}
	friend Ans operator+(const Ans&l,const Ans&r){
		Ans re;
		re.mn[0]=l.mn[0];
		re.mn[1]=inf;
		if(l.mn[1]<=r.mn[0])
			mini(re.mn[1],r.mn[1]);
		if(l.mn[1]<=r.mx[0])
			mini(re.mn[1],r.mx[1]);
		re.mx[0]=l.mx[0];
		re.mx[1]=inf;
		if(l.mx[1]<=r.mn[0])
			mini(re.mx[1],r.mn[1]);
		if(l.mx[1]<=r.mx[0])
			mini(re.mx[1],r.mx[1]);
		return re;
	}
};

#define N 200010
#define l(x) S[x].l
#define r(x) S[x].r
struct Node{
	int l,r;
	Ans x;
}S[N<<1];

int a[N],b[N],cnt;
inline int build(int tl,int tr){
	int q=++cnt;
	if(tl==tr){
		S[q].x.init(a[tl],b[tl]);
		return q;
	}
	int mid=(tl+tr)>>1;
	l(q)=build(tl,mid);
	r(q)=build(mid+1,tr);
	S[q].x=S[l(q)].x+S[r(q)].x;
	return q;
}

inline void modify(int q,int tl,int tr,int ins,int x,int y){
	if(tl==tr){
		S[q].x.init(x,y);
		return;
	}
	int mid=(tl+tr)>>1;
	if(ins<=mid)
		modify(S[q].l,tl,mid,ins,x,y);
	else
		modify(S[q].r,mid+1,tr,ins,x,y);
	S[q].x=S[l(q)].x+S[r(q)].x;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n=getint(),i,j;
	for(i=1;i<=n;++i){
		a[i]=getint();
		b[i]=getint();
	}
	build(1,n);
	int m=getint(),c,d,ca,cb,da,db;
	while(m--){
		c=getint();
		d=getint();
		ca=a[c],cb=b[c];
		da=a[d],db=b[d];
		modify(1,1,n,c,a[c]=da,b[c]=db);
		modify(1,1,n,d,a[d]=ca,b[d]=cb);
		if(S[1].x.mn[1]!=inf||S[1].x.mx[1]!=inf)
			puts("TAK");
		else
			puts("NIE");
	}
	return 0;
}