主席树

今天看了下主席树,感觉好神奇,代码精简而且实用,例如静态区间第k大之类的题,用主席树直接秒杀线段树套平衡树之类的写法。就是空间有点大。。
具体请参考:
1.clj的论文
2.博文一篇,代码写的很精炼:http://im.librazy.org/article/837/note-chairtree-via-functional-segtree/
其实很好理解的。
入门题:
hdu2665
静态区间第k小,注意题目描述可能不恰当。。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define w(i) T[(i)].w
#define lson(i) T[(i)].l
#define rson(i) T[(i)].r
using namespace std;
const int maxn=1e5+10;
int n,m;
int a[maxn],p[maxn],b[maxn];
bool cmp(int i,int j)
{
    return a[i]<a[j];
}
typedef struct Node{
    int l,r,w;
    Node(){l=r=w=0;}
}Node;
Node T[maxn*20];
int root[maxn],sz;
void ins(int &i,int l,int r,int x)
{
    T[++sz]=T[i];i=sz;
    w(i)++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(x<=m) ins(lson(i),l,m,x);
    else ins(rson(i),m+1,r,x);
}
int query(int i,int j,int l,int r,int k)
{
    if(l==r) return l;
    int t=w(lson(j))-w(lson(i));
    int m=(l+r)>>1;
    if(t>=k) return query(lson(i),lson(j),l,m,k);
    else return query(rson(i),rson(j),m+1,r,k-t);
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++) {scanf("%d",&a[i]);p[i]=i;}
        sort(p+1,p+1+n,cmp);
        for(i=1;i<=n;i++) b[p[i]]=i;
        root[0]=0;sz=0;
        for(i=1;i<=n;i++)
        {
            root[i]=root[i-1];
            ins(root[i],1,n,b[i]);
        }
        int l,r,k;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&l,&r,&k);
            int tmp=query(root[l-1],root[r],1,n,k);
            printf("%d\n",a[p[tmp]]);
        }
    }
    return 0;
}

类似积分

题目:给你三种图形,圆心在x轴上的圆,中心在x轴上且边与x轴平行的正方形,中心在x轴上且边与x轴成45度的正方形。三种图形的边长、半径都是<=10的非负数。且中心坐标是绝对值<=10的整数。给你n个图形(n<=10),问你共覆盖了多少面积,精确到整数位
思路:这题比赛时没多想,其实抓住答案的精度非常粗略且图形很少,范围很小就比较好做了。用积分的思想,x从-20递增到20,每次增长0.001,对于特定的x,枚举所有图形,找到最大的y,y*0.001就是这个小矩形区域的面积,累加*2即可。

#include<stdio.h>
#include<string.h>
#include<math.h>
inline double max(double a,double b){return a>b?a:b;}
int n;
typedef struct Node{
    int type;
    double x,d;
}Node;
Node node[12];
double cal(double x)
{
    int i;
    double y=0;
    for(i=1;i<=n;i++)
    {
        int type=node[i].type;
        double c=node[i].x,d=node[i].d;
        if(type==1)
        {
            if(c-d/2<=x && x<=c+d/2) y=max(y,d/2);
        }
        if(type==2)
        {
            double x1=c-d/sqrt(2.0),x2=c+d/sqrt(2.0);
            if(x1<x && x<=c) y=max(y,x-x1);
            if(c<x && x<=x2) y=max(y,x2-x);
        }
        if(type==3)
        {
            if(c-d<=x && x<=c+d) y=max(y,sqrt(d*d-(x-c)*(x-c)));
        }
    }
    return y;

}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t–)
    {
        scanf("%d",&n);
        char com[5];
        for(i=1;i<=n;i++)
        {
            scanf("%s%lf%lf",com,&node[i].x,&node[i].d);
            node[i].type=com[0]-’A'+1;
        }
        double ans=0;
        for(double x=-20;x<20;x+=0.001) ans+=0.001*cal(x);
        printf("%.0f\n",ans*2);


    }
    return 0;
}

cf375D Tree and Queries

昨天学了莫队算法,发现真的是很神奇,特别是简化版的,按sqrt(n)分块的算法,非常好写。这道题是佳神推荐的,发现确实很好,写下题解,大牛请直接关闭本页。。
题意:题目的意思是给你一棵树,每个节点都有一个正整数值。然后给你m个询问,每次询问你一棵子树中出现次数至少为kj次的数有多少个。题目中所有数都是<=10^5
思路:这题其实是前面写的树那题和分块那题的结合。首先dfs这棵树,得到dfs序。
于是问题转化为:给出一个长为n的序列,m个询问,每次询问[l,r]上有多少个数出现次数至少为qi次
这个问题可以这样:用一个数组cn[i],表示数i出现的次数。再用一个树状数组cc[],其中第i个元素表示出现次数为i次的数有几个。然后就是前面所讲的分块算法了,这在《莫队算法相关》这篇文章里讲过了。每次单步转移(也就是类似[l,r]->[l,r+1]的转移),需要更新cn[],时间是O(1),更新cc[],时间O(lgn).求解时计算getsum(n)-getsum(qi-1),时间为O(lgn).这样复杂度是O((n^1.5)lgn),n=1e5.算了一下大概在5*10^8左右。开始用线段树出现次数为x的数的个数,结果TLE,改成树状数组就过了,不过应该是数据不卡O((n^1.5)lgn)的原因,因为正解貌似是O(n^1.5)的。。待进一步思考
ps:del和insert的时候,少写了if,导致有时候一个数删去之后出现了0次,这时候对出现0次的数的个数+1,结果就出错了。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=1e5+5;
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[maxn*2];
int head[maxn],cnt;
bool visit[maxn];
int n,m,num;
int c[maxn],d[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
typedef struct Node{
    int begin,end;
}Node;
Node node[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);

    }
    node[cur].end=num;
    return;
}
typedef struct Q{
    int l,r,id,count,g;
}Q;
Q q[maxn];
int cn[maxn],ans[maxn];
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
/**
int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return sum[id];
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
**/
//树状数组部分
int cc[maxn];
int lowbit(int x)
{
	return x & -x;
}
void add2(int id,int x)
{
	for(int i=id;i<=n;i+=lowbit(i))
		cc[i]+=x;
	return;
}
int getsum(int x)
{
	int sum=0;
	for(int i=x;i>=1;i-=lowbit(i))
		sum+=cc[i];
	return sum;
}
//区间询问转移
void del(int x)
{
    if(cn[d[x]]) {add2(cn[d[x]],-1);cn[d[x]]--;}

    if(cn[d[x]]) add2(cn[d[x]],1);
}
void insert(int x)
{
    if(cn[d[x]]) add2(cn[d[x]],-1);
    cn[d[x]]++;
    if(cn[d[x]]) add2(cn[d[x]],1);
}

void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(cn,0,sizeof(cn));
        //memset(sum,0,sizeof(sum));
        memset(cc,0,sizeof(cc));
        for(i=1;i<=n;i++) scan(c[i]);
        for(i=1;i<=n-1;i++) {scan(a);scan(b);add(a,b);}
        dfs(1);
        for(i=1;i<=n;i++) d[node[i].begin]=c[i];
        int x,y;
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=m;i++)
        {
            scan(x);scan(y);
            q[i].l=node[x].begin;
            q[i].r=node[x].end;
            q[i].id=i;
            q[i].count=y;
            q[i].g=q[i].l/len+1;
        }
        sort(q+1,q+1+m,cmp);
        int curl=0,curr=0;
        for(i=1;i<=m;i++)
        {
            int l=q[i].l,r=q[i].r;
            while(curr<r)
            {
                curr++;
                insert(curr);
            }
            while(curr>r)
            {
                del(curr);
                curr--;
            }
            while(curl<l)
            {
                if(curl) del(curl);
                curl++;
            }
            while(curl>l)
            {
                curl--;
                insert(curl);
            }
            if(q[i].count>n) ans[q[i].id]=0;
            else ans[q[i].id]=getsum(n)-getsum(q[i].count-1);
        }
        for(i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}
/*
10 1
82 48 59 48 32 83 34 46 47 79
2 1
3 1
4 3
5 4
6 1
7 2
8 3
9 2
10 2
4 1
*/

莫队算法相关

分块?

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 17   Accepted Submission(s) : 6

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给定n个数,记为ai(1<=i <= n),求区间内某两个数和为给定的sum的对数。

Input

  第一行输入整数T,表示共有T组.
  接下来共T组,首先输入n,sum分别表示共n个数以及给定的和,再下一行依次输入n个数ai,然后输入一个q,表示共有q个询问,接下来q行每行输入l,r,表示要求的是区间[l,r].

范围:
T<=20
n <= 20000,sum <= 20000
1 <= ai < sum
q <= 20000,1<= l < r <= n

Output

  输出q行,回答每个询问的值.

Sample Input

1
4 4
1 2 2 3
3
1 2
2 3
1 4

Sample Output

0
1
2

Source

test

关于莫队算法,个人觉得这篇讲的比较通俗易懂,关于复杂度上界O(n^1.5)也证明的比较详细。。(大致上来说就是按左边界分块且每块内按右边界排列之后,将每次r的转移最坏O(n),变成一个块内的询问转移完毕最坏O(n),l的转移总复杂度可以类似分析)
真正的莫队算法是要求最小曼哈顿生成树的,但是其实有一种简洁的分块方法,具体见上面链接中的文章
其实突然发现自己以前是碰到过这种分块题目的,在一片论文中讲了一种支持修改的动态rmq算法,就是分块的,每次询问时sqrt(n),自己还写了模板,坑爹啊,全忘光了。。
这里还是简述下怎么分块:将长度为n的数列划分成每段长为sqrt(n)的一些段,这样可以保证复杂度上界是O(n^1.5)(当然前提是单步转移是O(1),如果是lgn,那么总复杂度是O((n^1.5)*lgn))。证明见上面说的文章,里面讲的很清楚。
这道题的话,数的范围在20000以内,所以可以用一个数组cnt[i],表示数i出现了几次。这样从(l,r)转移到(l,r+1)是O(1)的。像这种单步转移能做到O(1)或者O(lgn)的,都可以用莫队算法来搞。然后先O(n)算出第一个询问的答案,之后转移到第二个询问的时候,要注意如果是较少一个数,也就是差不多(l,r)->(l+1,r)这种转移类型,那么如果data[l]等于sum-data[l]时注意特判,因为这时候减少的对数不是cnt[sum-data[l]],而是cnt[sum-data[l]]-1。(试想,现在有3个2,sum为4,那么有3对数它们的和为4,然后减少一个2,显然减少了2对,而不是3对)

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct Query{
    int l,r,g,num,ans;
}Q;
Q q[20010];
int n,sum,data[20010],m;
bool cmp(Q a,Q b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
bool cmp2(Q a,Q b)
{
    return a.num<b.num;
}
int cnt[20010];
void cal(Q &a,Q &b)
{
    int i,tmp=a.ans;
    int l1=a.l,r1=a.r,l2=b.l,r2=b.r;
    if(r1<=l2 || r2<=l1)
    {
        for(i=l1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=l2;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l1<=l2 && l2<=r1 && r1<=r2)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    else if(l2<=l1 && l1<=r2 && r2<=r1)
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else if(l1<=l2 && r2<=r1)
    {
        for(i=l1;i<=l2-1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
        for(i=r2+1;i<=r1;i++) (data[i]*2==sum?tmp-=(cnt[sum-data[i]]-1):tmp-=cnt[sum-data[i]]),cnt[data[i]]--;
    }
    else
    {
        for(i=l2;i<=l1-1;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=r1+1;i<=r2;i++) tmp+=cnt[sum-data[i]],cnt[data[i]]++;
    }
    b.ans=tmp;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&sum);
        memset(cnt,0,sizeof(cnt));
        int len=(int)sqrt(n*1.0);
        //int cnt=(len*len==n?len:len+1);
        for(i=1;i<=n;i++) scanf("%d",&data[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].g=q[i].l/len+1;
            q[i].num=i;q[i].ans=0;
        }
        sort(q+1,q+1+m,cmp);
        for(i=q[1].l;i<=q[1].r;i++) q[1].ans+=cnt[sum-data[i]],cnt[data[i]]++;
        for(i=2;i<=m;i++) cal(q[i-1],q[i]);
        sort(q+1,q+1+m,cmp2);
        for(i=1;i<=m;i++) printf("%d\n",q[i].ans);



    }
    return 0;
}

其他题目:
bzoj2038
poj3241
WC 2013 糖果公园
UVALive 3662 Another Minimum Spanning Tree
hdu5213

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29469

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给你一棵N个节点的树,其中1为根节点,每个节点有权值。一开始所有节点的权值均为0。现在我们要进行M次操作。
  一共有以下两种操作:
  1)1 u d 节点1到节点u的最短路径上的所有的节点(包括1,u)的权值增加d(1<=d<=300)
  2)2 u 查询节点u的权值

Input

  多组测试数据
  每组测试数据第一行有两个数N,M (1<=N,M<=60000)
  接下来N-1行 每行有两个数u,v (1<=u,v<=N且u!=v)表示节点u和节点v之间有一条边
  接下来M行,即M次操作,含义见题目描述

Output

  对于每个操作2,请输出u的权值

Sample Input

3 4
1 2
1 3
1 2 3
2 1
2 2
2 3

Sample Output

3
3
0

Source

test

昨天校赛,这题没想到思路,想到就很简单了。。这题很有意思
思路:如果给某个点加上一个值,从这个点到根的结点都要加上这个值,这样暴力肯定不行。以前做过把树求出dfs序,转化成线段树的题,但是那是对某棵子树的结点都加上一个值,那么这题如果dfs序的话,每次操作要加的那些结点在线段树中时不连续的,怎么解决呢
其实可以这样做,每次操作只修改该点的值,最后求点u的值,只要对以u为根的子树对应的区间求和就行了。。。
当然也可以用树状数组,我比较习惯线段树,虽然慢一些。。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=6e4+5;
typedef struct Edge{
    int to,next;
}Edge;
typedef struct Node{
    int begin,end;
}Node;
Edge edge[2*maxn];
Node node[maxn];
int head[maxn],cnt;

int sum[maxn<<2];
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];
}
void update(int id,int l,int r,int pos,int v)
{
    if(l==r)
    {
        sum[id]+=v;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) update(lson,l,m,pos,v);
    else update(rson,m+1,r,pos,v);
    pushup(id);
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R)
    {
        return sum[id];
    }
    int m=(l+r)/2;
    int ret=0;
    if(L<=m) ret+=query(lson,l,m,L,R);
    if(R>m) ret+=query(rson,m+1,r,L,R);
    return ret;
}
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
}
int n,m,num;
bool visit[maxn];
void dfs(int cur)
{
    visit[cur]=1;
    node[cur].begin=(++num);
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);
    }
    node[cur].end=num;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        int u,v;
        cnt=0;num=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        dfs(1);
        int c,x,d;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&c);
            if(c==1)
            {
                scanf("%d%d",&x,&d);
                update(1,1,n,node[x].begin,d);
            }
            if(c==2)
            {
                scanf("%d",&x);
                printf("%d\n",query(1,1,n,node[x].begin,node[x].end));
            }
        }

    }



    return 0;
}

zoj3765 Lights 平衡树

好吧,不得不承认,经过一个寒假的颓废啥都忘了。。
一道裸的splay,但是比赛的时候我一直觉得用splay维护gcd会不会出错。。。。因为我居然觉得旋转过程中gcd无法正确维护。。。。
思路:splay节点信息
on:节点是否是开灯状态
val0:该节点关灯时的值,如果该节点灯开着,那么val0=0,不影响结果。
val1:该节点开灯时的值,如果该节点灯关着,那么val1=0,不影响结果。
gcd0:以该节点为根的子树中所有状态为关的灯的gcd
gcd1:以该节点为根的子树中所有状态为开的灯的gcd
num[0]:以该节点为根的子树有多少个状态为关的灯
num[1]:以该节点为根的子树有多少个状态为开的灯
看来这个月要好好复习了。。。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 500000+100
#define inf 0x3f3f3f3f
inline int max(int a,int b){return a>b?a:b;}
int gcd(int a,int b)
{
    if(a<b) {int t=a;a=b;b=t;}
    return (b==0?a:gcd(b,a%b));
}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]

	int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
    int cnt;
    int val0[N],val1[N];
    int on[N];
    int gcd0[N],gcd1[N];
    int data[N],state[N];
    int num[N][2];
	void pushup(int x)
	{
		sz[x]=1+sz[LC]+sz[RC];//如果左子树为空,则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在,则指向空结点0,空节点的sz=0,不会造成错误
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+1-on[x];
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
	}

	void rotate(int x, bool f) //旋转
	{
		int y=fa[x];
		int z=fa[y];
		ch[y][!f]=ch[x][f];
		fa[ch[x][f]]=y;
		fa[x]=z;
		if(z)
		{
			ch[z][ch[z][1]==y]=x;
		}
		ch[x][f]=y;
		fa[y]=x;
		pushup(y);
	}

	void splay(int x, int g) //把结点x转到结点g下
	{
		int y=fa[x];
        while (y!=g)
        {
			int z=fa[y];
			bool f=(ch[y][0]==x);
			if (z!=g && f==(ch[z][0]==y))
			{
				rotate(y,f);
			}
			rotate(x,f);
			y=fa[x];
		}
		pushup(x);
		if(g==0)
		{
			root=x;
		}
	}

	void rotateto(int k,int g) {	//把第k个结点转到结点g下,从第0个开始,因为有附加结点
		int x=root;
		while (sz[LC]!=k)
		{
			if (k<sz[LC])
			{
				x=LC;
			} else
			{
				k-=(sz[LC]+1);
				x=RC;
			}
		}
		splay(x,g);
	}

	void newNode(int &x,int c,int flag)
	{
        x=++cnt;
        on[x]=flag;
        num[x][flag]=1;num[x][1-flag]=0;
        if(!flag) val0[x]=c,val1[x]=0;
        else val1[x]=c,val0[x]=0;
        LC=RC=fa[x]=0;
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        sz[x]=1;
	}

	void makeTree(int &x,int l,int r,int f)
	{
		if (l>r)
		{
			return;
		}
		int m=(l+r)>>1;
		newNode(x,data[m],state[m]);	/*num[m]权值改成题目所需的*/
		makeTree(LC,l,m-1,x);
		makeTree(RC,m + 1,r,x);
		fa[x]=f;
		pushup(x);//建立树的时候,从下往上依次pushup
	}
	void init(int n)
	{
		cnt=0;
		ch[0][0]=ch[0][1]=fa[0]=sz[0]=num[0][0]=num[0][1]=val0[0]=on[0]=val1[0]=gcd0[0]=gcd1[0]=0;//0结点是空节点,代表没有
		//为了方便处理边界,加两个边界顶点
		newNode(root,0,0);
		newNode(ch[root][1],0,0);//这两个边界结点的值不影响正常求解
		fa[cnt]=root;
		sz[root]=2;
		makeTree(KT,1,n,ch[root][1]);
		pushup(ch[root][1]);
		pushup(root);
	}
	int query(int l,int r,int flag)
	{
        rotateto(l-1,0);
        rotateto(r+1,root);
        if(num[KT][flag]==0) return -1;
        return (flag==1?gcd1[KT]:gcd0[KT]);
    }
    void insert(int id,int v,int flag)
    {
        rotateto(id,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        newNode(LC,v,flag);
        fa[LC]=x;
        pushup(x);
        pushup(root);
    }
    void remove(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        //fa[LC]=0;
        LC=0;
        pushup(x);
        pushup(root);
    }
    void swap2(int &a,int &b)
    {
        int t=a;a=b;b=t;
    }
    void swap(int x)
    {
        on[x]=1-on[x];
        swap2(val0[x],val1[x]);
        gcd0[x]=gcd(gcd(gcd0[LC],gcd0[RC]),val0[x]);
        gcd1[x]=gcd(gcd(gcd1[LC],gcd1[RC]),val1[x]);
        num[x][0]=num[LC][0]+num[RC][0]+(1-on[x]);
        num[x][1]=num[LC][1]+num[RC][1]+on[x];
    }
    void rev(int id)
    {
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        swap(KT);
        pushup(x);
        pushup(root);
    }
    void modify(int id,int v)
	{
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        if(on[LC]==1) val1[LC]=v;
        else val0[LC]=v;
        gcd0[LC]=gcd(gcd(gcd0[ch[LC][0]],gcd0[ch[LC][1]]),val0[LC]);
        gcd1[LC]=gcd(gcd(gcd1[ch[LC][0]],gcd1[ch[LC][1]]),val1[LC]);
        pushup(x);
        pushup(root);
        return;
	}
	void print(int x)
	{
	    if(sz[x]==0) return;
        print(LC);
        printf("on:%d    val0:%d    val1:%d    gcd0:%d   gcd1:%d\n",on[x],val0[x],val1[x],gcd0[x],gcd1[x]);
        print(RC);
	}
	void debug(int x)
	{
        print(x);
        printf("\n");
	}
}spt;
int main()
{
    int i,j;
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            scanf("%d%d",&spt.data[i],&spt.state[i]);
        spt.init(n);
        char com[5];
        int a,b,state;
        while(m--)
        {
            scanf("%s",com);
            if(com[0]=='Q')
            {
                scanf("%d%d%d",&a,&b,&state);
                printf("%d\n",spt.query(a,b,state));
            }
            if(com[0]=='I')
            {
                scanf("%d%d%d",&a,&b,&state);
                spt.insert(a,b,state);
            }
            if(com[0]=='D')
            {
                scanf("%d",&a);
                spt.remove(a);
            }
            if(com[0]=='R')
            {
                scanf("%d",&a);
                spt.rev(a);
            }
            if(com[0]=='M')
            {
                scanf("%d%d",&a,&b);
                spt.modify(a,b);

            }
            //spt.debug(spt.root);
        }
    }
    return 0;
}

zoj 3761 Easy billiards dfs树

这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有n(0<=n<=2000)个球,可以用一个球沿与x坐标轴或y坐标轴平行的方向打球,如果球A碰到球B,那么球A停在球B的地方,球B以与A相同的方向前进,如果B运动的方向前方没有球了,那么判定球B出局,否则球B会撞到球C,以此类推,但是一个球不能直接出局,它必须是被某个球撞击后出局。
思路:把“相邻的球”(即可以直接撞击的球)连边,可以发现,同一个连通快中的球最后只会剩一个,,所以建图后dfs之,形成dfs树,为了保证一个连通块中的点撞到只剩一个,所以只要从子节点撞向父节点即可(比如,(0,0)、(1,0)、(0,1)三个点,dfs之后(0,0)是父节点,另两个是子节点,如果这时从(0,0)撞向(1,0)或(0,1)就会出错)
代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct Edge{
    int to;
    int next;
}Edge;
typedef struct Point{
    int x,y;
    int num;
}Point;
Point p[2010];
Edge edge[8000+10];
int head[2010],cnt;
int x[2010],y[2010];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;edge[cnt].next=head[v];
    head[v]=cnt++;
    return;
}
int ansx[2010],ansy[2010];
char dir[2010][10];
int num;
bool visit[2010];
void dfs(int cur)
{
    visit[cur]=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs(v);
        ansx[++num]=x[v],ansy[num]=y[v];
        if(x[v]==x[cur])
        {
            if(y[v]>y[cur]) strcpy(dir[num],"DOWN");
            else strcpy(dir[num],"UP");
        }
        else if(y[v]==y[cur])
        {
            if(x[v]>x[cur]) strcpy(dir[num],"LEFT");
            else strcpy(dir[num],"RIGHT");
        }
    }
    return;
}
bool cmp1(Point a,Point b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(Point a,Point b)
{
    if(a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        num=cnt=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            p[i].x=x[i];p[i].y=y[i];p[i].num=i;
        }
        sort(p+1,p+1+n,cmp1);
        for(i=2;i<=n;i++)
        {
            if(p[i].x==p[i-1].x) add(p[i-1].num,p[i].num);
        }
        sort(p+1,p+1+n,cmp2);
        for(i=2;i<=n;i++)
        {
            if(p[i].y==p[i-1].y) add(p[i-1].num,p[i].num);
        }
        memset(visit,0,sizeof(visit));
        for(i=1;i<=n;i++)
        {
            if(visit[i]) continue;
            dfs(i);
        }
        printf("%d\n",n-num);
        for(i=1;i<=num;i++) printf("(%d, %d) %s\n",ansx[i],ansy[i],dir[i]);
    }
    return 0;
}