Ryan_<

线段树应用：

1）维护连通性

bzoj1018: 【SHOI2008】堵塞的交通traffic

#include<bits/stdc++.h>
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define mec(a,x) memset(a,x,sizeof(a))
#define inf 1<<30
//time:4-20
using namespace std;
const int N=200000+10;//注意*2
typedef long long LL;
bool lnk[2][N];
int n,r1,r2,c1,c2;
char s[5];
struct node{int l,r,h1,h2,s1,s2,x1,x2;}t[N*5];
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
/*一开始考虑合并的时候，感觉路线非常非常多。其实要谨记一点：
要合并的两个区间该连的都已经连好了，
当前区间的合并只要考虑使用两个区间的交界就可以了*/
node merge(node x,node y)
{
	if(x.l==y.l && x.r==y.r) return x;//同一个
	node a;
	bool f1=lnk[1][x.r],f2=lnk[2][x.r];
	a.h1=(x.h1&f1&y.h1)|(x.x1&f2&y.x2);
	a.h2=(x.h2&f2&y.h2)|(x.x2&f1&y.x1);
	a.s1=x.s1|(x.h1&f1&y.s1&f2&x.h2);//绕一圈!
	a.s2=y.s2|(y.h1&f1&x.s2&f2&y.h2);//但是只绕对应的边(s1-s1,s2-s2)
	a.x1=(x.h1&f1&y.x1)|(x.x1&f2&y.h2);
	a.x2=(x.h2&f2&y.x2)|(x.x2&f1&y.h1);
	a.l=x.l;a.r=y.r;//注意!a.r=y.r
	return a;
}
void build(int k,int l,int r)
/*
  每个单位格对应线段树上一个单位线段
  这样写
*/
{
	if(l==r){t[k]=(node){l,r,1,1,0,0,0,0};return;}
	t[k].l=l;t[k].r=r;
	int mid=l+r>>1;
	build(lson);build(rson);
	t[k]=merge(t[k<<1],t[k<<1|1]);//??有无必要?
}
//线段树单点修改操作
void change(int k,int p,int d,bool f)
{
	if(t[k].l==t[k].r){
		if(d==3) t[k]=(node){t[k].l,t[k].r,1,1,f,f,f,f};
		else lnk[d][t[k].l]=f;
		return;
	}
	int mid=t[k].l+t[k].r>>1;
	if(p<=mid) change(k<<1,p,d,f);
	else change(k<<1|1,p,d,f);
	t[k]=merge(t[k<<1],t[k<<1|1]);
}
void modify(bool f)//分类讨论
{
	if(r1!=r2) change(1,c1,3,f);//只修改第一行
	else change(1,min(c1,c2),r1,f);//修改前面的
}
node find(int k,int L,int R)
/*查询区间用大写吧*/
{
//	if(R<t[k].l && t[k].r<L) return;
	if(L<=t[k].l && t[k].r<=R) return t[k];
	int mid=t[k].l+t[k].r>>1;
	if(R<=mid) return find(k<<1,L,R);
	if(L>mid) return find(k<<1|1,L,R);
	return merge(find(k<<1,L,R),find(k<<1|1,L,R));
}
bool ask(int r1,int c1,int r2,int c2)
{
	node a1=find(1,1,c1),a=find(1,c1,c2),a2=find(1,c2,n);
	//找到对应线段树中线段(结点)
	a.s1^=a1.s2;a.s2^=a2.s1;//注意!!!
	if(r1==r2){//在同一行:直接相连/
		if(r1==1) return a.h1|(a.s1&a.h2&a.s2)|(a.x1&a.s2)|(a.s1&a.x2);//在第一行
		else return a.h2|(a.s1&a.h1&a.s2)|(a.s1&a.x1)|(a.s2&a.x2);//在第二行
	}//在不同行:也要注意分类讨论!
	else if(r1<r2) return a.x1|(a.h1&a.s2)|(a.h2&a.s1);
	return a.x2|(a.s1&a.h1)|(a.s2&a.h2);
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("traffic.txt", "r", stdin);
//	freopen("apio2015.txt", "w", stdout);
	#endif
	scanf("%d",&n);
	build(1,1,n);
	while(scanf("%s",s)==1 && s[0]!='E'){
		scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
		if(s[0]=='A') puts(ask(r1,c1,r2,c2)?"Y":"N");
		else modify(s[0]=='O');
	}
	return 0;
}

2）小Q与内存

资瓷：插入、删除内存段，查询第i个内存段的第j个字符

#include<bits/stdc++.h>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 200010
#define inf (1<<30) 
using namespace std;
int tot,empty;
int root[maxn];
struct tree_type{int l,r,nl,nr,size,rnk;}t[maxn];//nl,nr为该节点对应区间的左右端点 
inline 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;
}
inline int newnode(int nl,int nr)//树中每个节点表示一段内存,可能会改变 
{
    tot++;
    t[tot].nl=nl;t[tot].nr=nr;//内存的左右端点 
    t[tot].l=t[tot].r=0;
    t[tot].size=nr-nl+1; 
    t[tot].rnk=(rand()<<15)+rand();///???
    return tot;
}
inline void pushup(int x)
{
    t[x].size=t[x].nr-t[x].nl+1;
    if (t[x].l) t[x].size+=t[t[x].l].size;
    if (t[x].r) t[x].size+=t[t[x].r].size;
}
inline int split(int x,int k,int &y)//分割点k的四种不同位置讨论  返回值??分割后k前子树 
{
    if (!x) return y=0,0;//y=0;return 0;??? 
    if (t[t[x].l].size>=k)
    {//在左子树中分割即可 
        int ret=split(t[x].l,k,t[x].l);
        y=x;pushup(y);/////
        return ret;
    }
    else if (t[t[x].l].size+t[x].nr-t[x].nl+1>k)
	//分割点k在当前区间节点内:将区间一分为二,原先的节点保存前半部分,新建一个结点保存后半部分 
    {
        k-=t[t[x].l].size;
        int pos=t[x].nl+k;
        y=newnode(pos,t[x].nr); 
        t[y].r=t[x].r;pushup(y);
        t[x].r=0;t[x].nr=pos-1;pushup(x); 
        return x;
    }
    else if (t[t[x].l].size+t[x].nr-t[x].nl+1==k)
    {
        y=t[x].r;
        t[x].r=0;pushup(x);///
        return x;
    }
    else
    {
        k-=t[t[x].l].size+t[x].nr-t[x].nl+1;//k=k-(t[t[x].l].size+t[x].nr-t[x].nl+1); 
        t[x].r=split(t[x].r,k,y);
        pushup(x);
        return x;
    }
}
inline int split2(int x,int k,int &y)//????
{
    if (!x) return y=0,0;
    if (k<t[x].nl)
    {
        int tmp=split2(t[x].l,k,t[x].l);
        y=x;pushup(y);return tmp;
    }
    else
    {
        t[x].r=split2(t[x].r,k,y);
        pushup(x);return x;
    }
}
inline int hebing(int x,int y)
{
    if (!x||!y) return x+y;
    if (t[x].rnk<t[y].rnk) swap(x,y);//???
    int tmp=split2(y,t[x].nl,y);
    t[x].l=hebing(tmp,t[x].l);
    t[x].r=hebing(y,t[x].r);
    pushup(x);
    return x;
}
inline bool alloc(int now,int x)
{
    if (t[empty].size<x) return false;
    root[now]=split(empty,x,empty);
    return true;
}
inline bool free(int now)
{
    if (!root[now]) return false;//不存在代表该段区间的节点 
    empty=hebing(empty,root[now]);
    root[now]=0;
    return true;
}
inline int kth(int x,int k)
{
    if (t[t[x].l].size>=k) return kth(t[x].l,k);
    else if (t[t[x].l].size+t[x].nr-t[x].nl+1>=k)
    {
        k-=t[t[x].l].size;
        return t[x].nl+k-1;
    }
    else return kth(t[x].r,k-(t[t[x].l].size+t[x].nr-t[x].nl+1));
}
int main()
{
    int tt=read();
    while (tt--)
    {
        int n=read(),now;
        tot=now=0;
        empty=newnode(0,inf);
        memset(root,0,sizeof(root));
        while (n--)
        {
            int opt=read();
            if (opt==1)
            {
                now++;//编号 
                int x=read();
                if (alloc(now,x)) puts("ok");
                else puts("failed");
            }
            else if (opt==2)
            {
                int x=read();
                if (free(x)) puts("ok");
                else puts("failed");
            }
            else
            {
                int x=read(),y=read()+1;//从1开始 
                if (!root[x]||t[root[x]].size<y) puts("failed");
                else printf("%d\n",kth(root[x],y));//注意是root[x]而非x!!????? 
            }
        }
    }
    return 0;
}

之后的任务：

3）学姐的钱包

4）mex