题目大意：求一个字符串中形如AABB的子串个数。

思路：用哈希做到O(1)判断字符串是否相同，O($n^2$)预处理，ans[i]为开头位置为i的形如AA的子串个数。再用O($n^2$)枚举出AABB中的AA，加上BB（已预处理）的个数即可。时间复杂度为O($n^2$),最后一个点过不掉~~。（此方法为在下所想的朴素算法，比不得大神们的方法，代码更是烂得要死）

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int S=999983,mod=100000009;
char s[40000];
long long ans[40000],Hash[40000],mi[40000];

int gethash(int l,int r)
{
    return (Hash[r]-Hash[l-1]*mi[r-l+1]%mod+mod)%mod;
}

int main()
{
    int n;
    scanf("%d",&n);
    while (n--)
    {
        int cnt,i,j;
        long long sum=0;
        scanf("%s",s+1); cnt=strlen(s+1);
        for (i=1;i<=cnt;i++) Hash[i]=(Hash[i-1]*S+s[i]-'a'+1)%mod;
        for (mi[0]=i=1;i<=cnt;i++) mi[i]=mi[i-1]*S%mod;
        for (i=1;i<=cnt;i++) ans[i]=0;
        for (i=1;i<=cnt;i++)
            for (j=i;j+j-i+1<=cnt;j++)
                if (gethash(i,j)==gethash(j+1,j+j-i+1)) ans[i]++;
        for (i=2;i<cnt-1;i++)
            for (j=i;j>i+1>>1;j--)
                if (gethash(j,i)==gethash(j-i+j-1,j-1)) sum+=ans[i+1];
        printf("%d\n",sum);
    }
    return 0;
}

题目大意：有n个区间，当有m个区间有公共部分时，求m个区间长度的最大值与最小值之差的最小值。

思路：按区间的长度从小到大排序，可知连续的几个区间最优，则用两个指针指其头尾，线性扫描，再用线段树区间覆盖。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 1000009
#define INF 2147483647
using namespace std;

int n,m,i,j,cnt,ans=INF,sum[N<<2],lazy[N<<2],b[N<<1];
struct node{ int l,r,len; } a[N];

bool cmp(const node &x,const node &y)
{
    return x.len<y.len;
}

int find(int l,int r,int x)
{
    if (l==r) return l;
    int mid=l+r>>1;
    if (x<=b[mid]) find(l,mid,x);
    else find(mid+1,r,x);
}

void up_date(int k,int x)
{
    sum[k]+=x,lazy[k]+=x;
}

void change(int cur,int L,int R,int l,int r,int val)
{
    if (L==l && R==r) { up_date(cur,val); return; }
    int mid=L+R>>1;
    if (lazy[cur])
    {
        up_date(cur<<1,lazy[cur]);
        up_date(cur<<1|1,lazy[cur]);
        lazy[cur]=0;
    }
    if (r<=mid) change(cur<<1,L,mid,l,r,val);
    else if (l>mid) change(cur<<1|1,mid+1,R,l,r,val);
         else change(cur<<1,L,mid,l,mid,val),change(cur<<1|1,mid+1,R,mid+1,r,val);
    sum[cur]=max(sum[cur<<1],sum[cur<<1|1]);
}

void solve()
{
    for (i=1;i<=n;i++)
    {
        while (sum[1]<m)
        {
            if (j==n) return; j++;
            change(1,1,cnt,a[j].l,a[j].r,1);
        }
        ans=min(ans,a[j].len-a[i].len);
        change(1,1,cnt,a[i].l,a[i].r,-1);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        b[++cnt]=a[i].l,b[++cnt]=a[i].r;
        a[i].len=a[i].r-a[i].l;
    }
    sort(a+1,a+n+1,cmp),sort(b+1,b+cnt+1);
    for (i=1;i<=n;i++) a[i].l=find(1,cnt,a[i].l),a[i].r=find(1,cnt,a[i].r);
    solve(); printf("%d\n",ans<INF?ans:-1);
    return 0;
}

题目大意：给定一棵有根树，每个点有一个权值，提供三种操作：

1.将x节点变为根节点

2.将x到y路径上的点的权值全部改为v

3.询问x的子树中点权的最小值

思路：用DFS序剖分，记录每个节点入栈出栈的时间，其之间的区间即为子树。操作2用线段树直接搞，而换根先不管，可用原来的DFS序。询问时分类讨论：记最开始的根为root，换根之后，对于当前的根rtnow和询问子树U而言，

①rtnow==U，询问整棵树

②fa[rtnow]==U，询问除了rtnow所在子树以外的整棵树

③rtnow在U的子树里，且距离大于1，询问除了rtnow的除了其祖先是U的儿子的祖先的子树以外的整棵树

④rtnow不在U的子树里，询问U的子树

代码：

#include<cstdio>
#include<iostream>
#define M 2000000
#define INF 2147483647
using namespace std;

int cnt,dfn,n,m,a[M],to[M],hson[M],next[M],head[M],id[M],size[M],last[M],pos[M],pa[M],deep[M],top[M],cov[M<<2],minv[M<<2];

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs1(int x)
{
    size[x]=1;
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x])
        {
            pa[to[i]]=x,deep[to[i]]=deep[x]+1;
            dfs1(to[i]),size[x]+=size[to[i]];
            if (size[to[i]]>size[hson[x]]) hson[x]=to[i];
        }
}

void dfs2(int x,int tp)
{
    id[x]=++dfn,pos[dfn]=x,top[x]=tp;
    if (hson[x]) dfs2(hson[x],tp);
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]);
    last[x]=dfn;
}

void push_down(int k)
{
     if (cov[k])
     {
         cov[k<<1]=cov[k<<1|1]=minv[k<<1]=minv[k<<1|1]=cov[k];
         cov[k]=0;
     }
}

void change(int cur,int L,int R,int l,int r,int val)
{
     if (L==l && R==r) { cov[cur]=minv[cur]=val; return; }
     int mid=L+R>>1; push_down(cur);
     if (r<=mid) change(cur<<1,L,mid,l,r,val);
     else if (l>mid) change(cur<<1|1,mid+1,R,l,r,val);
          else change(cur<<1,L,mid,l,mid,val),change(cur<<1|1,mid+1,R,mid+1,r,val);
     minv[cur]=min(minv[cur<<1],minv[cur<<1|1]);
}

int ask(int cur,int L,int R,int l,int r)
{
    if (L==l && R==r) return minv[cur];
    int mid=L+R>>1; push_down(cur);
    if (r<=mid) return ask(cur<<1,L,mid,l,r);
    if (l>mid) return ask(cur<<1|1,mid+1,R,l,r);
    return min(ask(cur<<1,L,mid,l,mid),ask(cur<<1|1,mid+1,R,mid+1,r));
}

void add(int x,int y,int val)
{
     for (;top[x]!=top[y];x=pa[top[x]])
     {
         if (deep[top[x]]<deep[top[y]]) swap(x,y);
         change(1,1,n,id[top[x]],id[x],val);
     }
     if (deep[x]>deep[y]) swap(x,y);
     change(1,1,n,id[x],id[y],val);
}

int main()
{
    scanf("%d%d",&n,&m);
    int i,x,y,z,op,rt,root=0;
    for (i=1;i<n;i++) scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&rt);dfs1(rt),dfs2(rt,rt);
    for (i=1;i<=n;i++) change(1,1,n,id[i],id[i],a[i]);
    while (m--)
    {
          scanf("%d",&op);
          if (op==1) scanf("%d",&root);
          if (op==2) scanf("%d%d%d",&x,&y,&z),add(x,y,z);
          if (op==3)
          {
               scanf("%d",&x);
               if (x==root) printf("%d\n",ask(1,1,n,1,n));
               else if (pa[root]==x) printf("%d\n",min(ask(1,1,n,1,id[root]-1),last[root]==n?INF:ask(1,1,n,last[root]+1,n)));
                    else if (id[root]>=id[x] && id[root]<=last[x])
                         {
                              y=root;
                              while (pa[top[y]]!=x && top[x]!=top[y]) y=pa[top[y]];
                              if (pa[top[y]]!=x) y=pos[id[x]+1];
                              else y=top[y];
                              printf("%d\n",min(ask(1,1,n,1,id[y]-1),last[y]==n?INF:ask(1,1,n,last[y]+1,n)));
                         }
                         else printf("%d\n",ask(1,1,n,id[x],last[x]));
          }
    }
    return 0;
}

题目大意：给出一个n个点的数，和m次操作。每个点有颜色和权值。 每次操作分4种 1：修改一个点的颜色 2：修改一个点的权值 3：询问从x到y的路径上，和x相同颜色的点的权值和（保证x，y同颜色） 4：询问从x到y的路径上，和x相同颜色的点的权值最大值（保证x，y同颜色）

思路：树链剖分，用线段树来维护和以及最大值。

代码：

#include<cstdio>
#include<iostream>
#define M 3000009
using namespace std;

int cnt,dfn,num,n,m,w[M],c[M],to[M<<1],next[M<<1],head[M],deep[M],size[M],pa[M],id[M],top[M],root[M],sum[M<<2],mx[M<<2],lc[M<<2],rc[M<<2];

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs1(int x)
{
     size[x]=1;
     for (int i=head[x];i;i=next[i])
         if (pa[x]!=to[i])
         {
              deep[to[i]]=deep[x]+1,pa[to[i]]=x;
              dfs1(to[i]),size[x]+=size[to[i]];
         }
}

void dfs2(int x,int chain)
{
     int i,k=0;
     id[x]=++dfn,top[x]=chain;
     for (i=head[x];i;i=next[i])
         if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i];
     if (!k) return; dfs2(k,chain);
     for (i=head[x];i;i=next[i])
         if (pa[x]!=to[i] && k!=to[i]) dfs2(to[i],to[i]);
}

void up_date(int k)
{
     sum[k]=sum[lc[k]]+sum[rc[k]];
     mx[k]=max(mx[lc[k]],mx[rc[k]]);
}

void change(int &cur,int l,int r,int x,int val)
{
     if (!cur) cur=++num;
     if (l==r) { sum[cur]=mx[cur]=val; return; }
     int mid=l+r>>1;
     if (x<=mid) change(lc[cur],l,mid,x,val);
     else change(rc[cur],mid+1,r,x,val);
     up_date(cur);
}

int ask_sum(int cur,int L,int R,int l,int r)
{
    if (!cur) return 0;
    if (L==l && R==r) return sum[cur];
    int mid=L+R>>1;
    if (r<=mid) return ask_sum(lc[cur],L,mid,l,r);
    if (l>mid) return ask_sum(rc[cur],mid+1,R,l,r);
    return ask_sum(lc[cur],L,mid,l,mid)+ask_sum(rc[cur],mid+1,R,mid+1,r);
}

int ask_max(int cur,int L,int R,int l,int r)
{
    if (!cur) return 0;
    if (L==l && R==r) return mx[cur];
    int mid=L+R>>1;
    if (r<=mid) return ask_max(lc[cur],L,mid,l,r);
    if (l>mid) return ask_max(rc[cur],mid+1,R,l,r);
    return max(ask_max(lc[cur],L,mid,l,mid),ask_max(rc[cur],mid+1,R,mid+1,r));
}

int Ask_Sum(int x,int y,int z)
{
    int ans=0;
    for (;top[x]!=top[y];x=pa[top[x]])
    {
        if (deep[top[x]]<deep[top[y]]) swap(x,y);
        ans+=ask_sum(root[z],1,n,id[top[x]],id[x]);
    }
    if (deep[x]>deep[y]) swap(x,y);
    return ans+ask_sum(root[z],1,n,id[x],id[y]);
}

int Ask_Max(int x,int y,int z)
{
    int ans=-10000000;
    for (;top[x]!=top[y];x=pa[top[x]])
    {
        if (deep[top[x]]<deep[top[y]]) swap(x,y);
        ans=max(ans,ask_max(root[z],1,n,id[top[x]],id[x]));
    }
    if (deep[x]>deep[y]) swap(x,y);
    return max(ans,ask_max(root[z],1,n,id[x],id[y]));
}

int main()
{
    scanf("%d%d",&n,&m);
    int i,x,y;
    for (i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
    for (i=1;i<n;i++) scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
    dfs1(1),dfs2(1,1);
    for (i=1;i<=n;i++) change(root[c[i]],1,n,id[i],w[i]);
    for (i=1;i<=m;i++)
    {
        char ch[9];
        scanf("%s%d%d",ch,&x,&y);
        if (ch[0]=='C')
            if (ch[1]=='C') change(root[c[x]],1,n,id[x],0),change(root[y],1,n,id[x],w[x]),c[x]=y;
            else change(root[c[x]],1,n,id[x],y),w[x]=y;
        else if (ch[1]=='S') printf("%d\n",Ask_Sum(x,y,c[x]));
             else printf("%d\n",Ask_Max(x,y,c[x]));
    }scanf("%d",&n);
    return 0;
}

题目大意：给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段）

思路:树剖之后，维护其两端的颜色、答案和标记即可。

代码：

#include<cstdio>
#include<iostream>
#define N 100001
using namespace std;
int n,m,cnt,dfn,vis[N],head[N],to[N<<1],next[N<<1],deep[N],size[N],top[N],id[N],v[N],pa[N],lazy[N<<2],lc[N<<2],rc[N<<2],sum[N<<2];

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs1(int x)
{
    size[x]=vis[x]=1;
    for (int i=head[x];i;i=next[i])
        if (!vis[to[i]])
        {
            deep[to[i]]=deep[x]+1;
            pa[to[i]]=x;
            dfs1(to[i]);
            size[x]+=size[to[i]];
        }
}

void dfs2(int x,int chain)
{
    int k=0,i;
    id[x]=++dfn;
    top[x]=chain;
    for (i=head[x];i;i=next[i])
        if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i];
    if (!k) return;
    dfs2(k,chain);
    for (i=head[x];i;i=next[i])
        if (deep[to[i]]>deep[x] && to[i]!=k) dfs2(to[i],to[i]);
}

void build(int l,int r,int cur)
{
    sum[cur]=1,lazy[cur]=-1;
    if(l==r)return;
    int mid=l+r>>1;
    build(l,mid,cur<<1),build(mid+1,r,cur<<1|1);
}

void update(int k)
{
    lc[k]=lc[k<<1],rc[k]=rc[k<<1|1];
    if (rc[k<<1]^lc[k<<1|1]) sum[k]=sum[k<<1]+sum[k<<1|1];
    else sum[k]=sum[k<<1]+sum[k<<1|1]-1;
}

void pushdown(int l,int r,int k)
{
    int tmp=lazy[k]; lazy[k]=-1;
    if (tmp==-1 || l==r) return;
    sum[k<<1]=sum[k<<1|1]=1;
    lazy[k<<1]=lazy[k<<1|1]=tmp;
    lc[k<<1]=rc[k<<1]=tmp;
    lc[k<<1|1]=rc[k<<1|1]=tmp;
}

void change(int L,int R,int l,int r,int cur,int val)
{
    if (l==L && r==R) { lc[cur]=rc[cur]=val; sum[cur]=1; lazy[cur]=val; return; }
    int mid=L+R>>1; pushdown(L,R,cur);
    if (r<=mid) change(L,mid,l,r,cur<<1,val);
    else if (l>mid) change(mid+1,R,l,r,cur<<1|1,val);
         else change(L,mid,l,mid,cur<<1,val),change(mid+1,R,mid+1,r,cur<<1|1,val);
    update(cur);
}


int ask(int L,int R,int l,int r,int cur)
{
    if (l==L && r==R) return sum[cur];
    int mid=L+R>>1; pushdown(L,R,cur);
    if (r<=mid) return ask(L,mid,l,r,cur<<1);
    else if (l>mid) return ask(mid+1,R,l,r,cur<<1|1);
         else
         {
              int tmp=1;
              if (rc[cur<<1]^lc[cur<<1|1]) tmp=0;
              return ask(L,mid,l,mid,cur<<1)+ask(mid+1,R,mid+1,r,cur<<1|1)-tmp;
         }
}

int getc(int l,int r,int cur,int x)
{
    if (l==r) return lc[cur];
    int mid=l+r>>1; pushdown(l,r,cur);
    if (x<=mid) return getc(l,mid,cur<<1,x);
    else return getc(mid+1,r,cur<<1|1,x);
}

int solvesum(int x,int y)
{
    int sum=0;
    for (;top[x]!=top[y];x=pa[top[x]])
    {
        if (deep[top[x]]<deep[top[y]]) swap(x,y);
        sum+=ask(1,n,id[top[x]],id[x],1);
        if (getc(1,n,1,id[top[x]])==getc(1,n,1,id[pa[top[x]]])) sum--;
    }
    if (deep[x]>deep[y]) swap(x,y);
    return sum+=ask(1,n,id[x],id[y],1);
}

void solvechange(int x,int y,int val)
{
    for (;top[x]!=top[y];x=pa[top[x]])
    {
        if (deep[top[x]]<deep[top[y]]) swap(x,y);
        change(1,n,id[top[x]],id[x],1,val);
    }
    if (deep[x]>deep[y]) swap(x,y);
    change(1,n,id[x],id[y],1,val);
}

int main()
{
    int i,a,b,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&v[i]);
    for(i=1;i<n;i++) scanf("%d%d",&a,&b),ins(a,b),ins(b,a);
    dfs1(1),dfs2(1,1),build(1,n,1);
    for(i=1;i<=n;i++) change(1,n,id[i],id[i],1,v[i]);
    for(i=1;i<=m;i++)
    {
        char ch[10];
        scanf("%s",ch);
        if(ch[0]=='Q')
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",solvesum(a,b));
        }
        else
        {
            scanf("%d%d%d",&a,&b,&c);
            solvechange(a,b,c);
        }
    }
    return 0;
}

题目大意：有n个软件安装包，除第一个以外，其他的要在另一个安装包的基础上安装，且无环，问在安装和卸载某个软件包时，这个操作实际上会改变多少个软件包的安装状态。

思路：可构成树，用树链剖分，线段树。已安装的为1，未安装的为0。

对于安装操作，就是询问x到0的路径上0的个数，然后把这个路径赋为1

对于卸载操作，就是询问x的子树中1的个数，然后把子树赋为0。

代码：

#include<cstdio>
#include<iostream>
#define M 800500
using namespace std;

int n,cnt,dfn,hson[M],pa[M],id[M],to[M],top[M],vis[M],last[M],next[M],head[M],deep[M],size[M],sum[M],sz[M],lazy[M];

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs1(int x)
{
    size[x]=1;
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x])
        {
            pa[to[i]]=x,deep[to[i]]=deep[x]+1;
            dfs1(to[i]),size[x]+=size[to[i]];
            if (size[to[i]]>size[hson[x]]) hson[x]=to[i];
        }
}

void dfs2(int x,int tp)
{
    id[x]=++dfn,top[x]=tp;
    if (hson[x]) dfs2(hson[x],tp);
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]);
    last[x]=dfn;
}

void build(int l,int r,int cur)
{
     if (l==r) { sum[cur]=0,lazy[cur]=-1,sz[cur]=1; return; }
     int mid=l+r>>1;
     build(l,mid,cur<<1),build(mid+1,r,cur<<1|1);
     sz[cur]=sz[cur<<1]+sz[cur<<1|1];
}

void push_down(int k)
{
     if (lazy[k]!=-1)
     {
          sum[k<<1]=sz[k<<1]*lazy[k],sum[k<<1|1]=sz[k<<1|1]*lazy[k];
          lazy[k<<1]=lazy[k<<1|1]=lazy[k],lazy[k]=-1;
     }
}

void change(int L,int R,int l,int r,int cur,int val)
{
     if (L==l && R==r) { sum[cur]=val*sz[cur]; lazy[cur]=val; return; }
     int mid=L+R>>1; push_down(cur);
     if (r<=mid) change(L,mid,l,r,cur<<1,val);
     else if (l>mid) change(mid+1,R,l,r,cur<<1|1,val);
          else change(L,mid,l,mid,cur<<1,val),change(mid+1,R,mid+1,r,cur<<1|1,val);
     sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}

int ask(int L,int R,int l,int r,int cur)
{
    if (L==l && R==r) return sum[cur];
    int mid=L+R>>1; push_down(cur);
    if (r<=mid) return ask(L,mid,l,r,cur<<1);
    else if (l>mid) return ask(mid+1,R,l,r,cur<<1|1);
         else return ask(L,mid,l,mid,cur<<1)+ask(mid+1,R,mid+1,r,cur<<1|1);
}

void add(int x,int y)
{
     if (deep[x]<deep[y]) swap(x,y);
     int sum=0,t=deep[x]-deep[y]+1;
     for (;top[x]!=top[y];x=pa[top[x]])
     {         
         if (deep[top[x]]<deep[top[y]]) swap(x,y);
         sum+=ask(1,n,id[top[x]],id[x],1);
         change(1,n,id[top[x]],id[x],1,1);
     }
     if (deep[x]>deep[y]) swap(x,y);
     sum+=ask(1,n,id[x],id[y],1);
     change(1,n,id[x],id[y],1,1);
     printf("%d\n",t-sum);
}

int main()
{
    int i,m,x;
    scanf("%d",&n);
    for (i=1;i<n;i++) scanf("%d",&m),ins(m+1,i+1);
    scanf("%d",&m),dfs1(1),dfs2(1,1),build(1,n,1);
    for (i=1;i<=m;i++)
    {
        char ch[20];
        scanf("%s%d",ch,&x),x++;
        if (ch[0]=='i') add(1,x);
        else printf("%d\n",ask(1,n,id[x],last[x],1)),change(1,n,id[x],last[x],1,0);
    }
    return 0;
}

题目大意：有一棵树，最先每条边的权值是1，然后给出n+m-1个操作，操作有两种：1.询问一个点到根的路径上的权值和；2.将一条边的权值改为0.

思路：用dfs序将树化为序列，在dfs序中我们会保存节点i进入时间come[i]和出去时间leave[i]，这两个数之间的区间即为其子树。询问实为前缀和，可用树状数组记录。修改只会影响其子树（即区间），其他部分并不会改变（+1-1抵消了）。

代码：

#include<cstdio>
#include<iostream>
#define M 300000 
using namespace std;

int n,m,cnt,dfn,to[M],next[M],head[M],c[M],come[M],leave[M];

int read()
{
    int x=0,y=1;
    char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*y;
}

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs(int x)
{
     come[x]=++dfn;
     for (int i=head[x];i;i=next[i]) dfs(to[i]);
     leave[x]=dfn;
}

void add(int x,int y)
{
     for (;x<=n;x+=x&-x) c[x]+=y;
}

int sum(int x)
{
    int ans=0;
    for (;x;x-=x&-x) ans+=c[x];
    return ans;
}

int main()
{
    int i,j,x,y;
    n=read();
    for (i=1;i<n;i++) x=read(),y=read(),ins(x,y);
    dfs(1);
    m=read();
    for (i=2;i<=n;i++) add(come[i],1),add(leave[i]+1,-1);
    for (i=1;i<n+m;i++)
    {
        char ch=getchar();
        while (ch<'A' || ch>'Z') ch=getchar();
        if (ch=='W') printf("%d\n",sum(come[read()]));
        else x=read(),y=read(),add(come[y],-1),add(leave[y]+1,1);
    }scanf("%d",&n);
    return 0;
}

题目大意：有一个长度为n的序列，有三个操作1.I a b c表示将[a,b]这一段区间的元素集体增加c，2.R a b表示将[a,b]区间内所有元素变成相反数，3.Q a b c表示询问[a,b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。

思路：显然需要用线段树维护一个数组sum[c]表示选c个数相乘的方案总和。合并的时候只要枚举c，然后枚举左边选几个数然后和右边的乘起来累加进去就好了。取反实际上就是把所有c为奇数的取反，关键是区间加。对于[l,r]，区间+x，那么枚举c。注意到形式是这样的： newsum[c]=Σ(a1+x)(a2+x)...(ac+x)，然后按照x的次数合并同类项，可以发现这个东西可以通过x^k，组合数C(r-l+1,k)和oldsum[c-k]得到答案。k为x的次数。其余就是普通的线段树了。注意：推标记时要注意顺序。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 150000
#define mod 19940417
#define ll long long
using namespace std;

int lazy[N],zhs[N][21],size[N];
struct node{int sum[21];}ans[N];
bool rev[N];

int read()
{
    int x=0,y=1;
    char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*y;
}

void add(int &x,int y)
{
    x+=y;
    if (x>=mod) x-=mod;
}

void up_date(int k)
{
     for (int i=1;i<=20;i++)
     {
         ans[k].sum[i]=0;
         for (int j=1;j<i;j++) add(ans[k].sum[i],(ll)ans[k<<1].sum[j]*ans[k<<1|1].sum[i-j]%mod);
         add(ans[k].sum[i],ans[k<<1].sum[i]);add(ans[k].sum[i],ans[k<<1|1].sum[i]);
     }
}

void ins(int k,int val)
{
     add(lazy[k],val);
     for (int i=20;i;i--)
     {
         int x=val,j;
         for (j=i-1;j;j--,x=(ll)x*val%mod)
             add(ans[k].sum[i],(ll)x*ans[k].sum[j]%mod*zhs[size[k]-j][i-j]%mod);
         add(ans[k].sum[i],(ll)x*zhs[size[k]][i]%mod);
     }
}

void turn(int k)
{
    int i; rev[k]^=1;
    if (lazy[k]) lazy[k]=mod-lazy[k];
    for (i=19;i>0;i-=2) if (ans[k].sum[i]) ans[k].sum[i]=mod-ans[k].sum[i];
}

void build(int l,int r,int cur)
{
     size[cur]=r-l+1;
     if (l==r) {ans[cur].sum[1]=read()%mod;return;}
     int mid=(l+r)>>1;
     build(l,mid,cur<<1),build(mid+1,r,cur<<1|1),up_date(cur);
}

void push_down(int k)
{
    if (rev[k]) turn(k<<1),turn(k<<1|1),rev[k]=0;
    if (lazy[k])ins(k<<1,lazy[k]),ins(k<<1|1,lazy[k]),lazy[k]=0;
}


void fan(int l,int r,int k,int x,int y)
{
    if (l==x && r==y){ turn(k); return; }
    int mid=l+r>>1; push_down(k);
    if (y<=mid) fan(l,mid,k<<1,x,y);
    else if (x>mid) fan(mid+1,r,k<<1|1,x,y);
         else fan(l,mid,k<<1,x,mid),fan(mid+1,r,k<<1|1,mid+1,y);
    up_date(k);
}

void jia(int L,int R,int cur,int l,int r,int val)
{
    if (l==L && r==R) {ins(cur,val);return;}
    int mid=(L+R)>>1; push_down(cur);
    if (r<=mid) jia(L,mid,cur<<1,l,r,val);
    else if (l>mid) jia(mid+1,R,cur<<1|1,l,r,val); 
         else jia(L,mid,cur<<1,l,mid,val),jia(mid+1,R,cur<<1|1,mid+1,r,val);
    up_date(cur);
}

node ask(int L,int R,int cur,int l,int r,int val)
{
     if (l==L && r==R) return ans[cur];
     int mid=(L+R)>>1; push_down(cur);
     if (l>mid) return ask(mid+1,R,cur<<1|1,l,r,val);
     else if (r<=mid) return ask(L,mid,cur<<1,l,r,val);
          else
          {
              node x=ask(L,mid,cur<<1,l,mid,val),y=ask(mid+1,R,cur<<1|1,mid+1,r,val),t;
              for (int i=1;i<=val;i++)
              {
                  t.sum[i]=(x.sum[i]+y.sum[i])%mod;
                  for (int j=1;j<i;j++) add(t.sum[i],(ll)x.sum[j]*y.sum[i-j]%mod);
              }
              return t;
          }
}

int main()
{
    int n=read(),m=read(),i,j;
    zhs[0][0]=1;
    for (i=1;i<=n;i++)
    {
        zhs[i][0]=1;
        for (j=1;j<=i && j<=20;j++) zhs[i][j]=(zhs[i-1][j-1]+zhs[i-1][j])%mod;
    }
    build(1,n,1);
    while (m--)
    {
          char ch=getchar();
          while (ch<'A' || ch>'Z') ch=getchar();
          if (ch=='I')
          {
               int x=read(),y=read(),z=read()%mod;
               if (z<0) z+=mod; jia(1,n,1,x,y,z);
          }
          if (ch=='R')
          {
              int x=read(),y=read();
              fan(1,n,1,x,y);
          }
          if (ch=='Q')
          {
              int x=read(),y=read(),z=read();
              printf("%d\n",ask(1,n,1,x,y,z).sum[z]);
          }
    }
    return 0;
}

题目大意：给定一棵n个点的树，每个点有一个权值，m个询问，每次询问树上点x到点y的路径上的第k小数。

思路：dfs后给每个节点一个dfs序，以每个点在他父亲的基础上建立主席树，询问时用(点x+点y-点lca(x,y)-点dad[lca(x,y)])即可得到x到y的链，在上面查询即可。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200009
using namespace std;

int tot=1,dfn,num,cnt,pa[N][18],to[N],next[N],head[N],lc[N*10],rc[N*10],deep[N],sum[N*10],id[N],pos[N],root[N],a[N],b[N];

int read()
{
    int x=0,y=1;char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*y;
}

void add(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs(int x)
{
     int i;id[x]=++dfn,pos[dfn]=x;
     for (i=1;i<=16;i++)
         if ((1<<i)<=deep[x]) pa[x][i]=pa[pa[x][i-1]][i-1];
         else break;
     for (i=head[x];i;i=next[i])
         if (pa[x][0]!=to[i])
         {
              deep[to[i]]=deep[x]+1;
              pa[to[i]][0]=x;
              dfs(to[i]);
         }
}

void change(int l,int r,int x,int &cur,int _cur)
{
     cur=++num;
     lc[cur]=lc[_cur];
     rc[cur]=rc[_cur];
     sum[cur]=sum[_cur]+1;
     if (l==r) return;
     int mid=l+r>>1;
     if (x<=b[mid]) change(l,mid,x,lc[cur],lc[_cur]);
     else change(mid+1,r,x,rc[cur],rc[_cur]);
}

int LCA(int x,int y)
{
    if (deep[x]<deep[y]) swap(x,y);
    int i,t=deep[x]-deep[y];
    for (i=0;i<=16;i++)
        if ((1<<i)&t) x=pa[x][i];
    for (i=16;i>=0;i--)
        if (pa[x][i]!=pa[y][i]) x=pa[x][i],y=pa[y][i];
    if (x==y) return x;
    return pa[x][0];
}

int ask(int x,int y,int k)
{
    int a=root[id[x]],b=root[id[y]],c=LCA(x,y),d=pa[c][0],l=1,r=tot;
    c=root[id[c]],d=root[id[d]];
    while (l<r)
    {
          int t=sum[lc[a]]+sum[lc[b]]-sum[lc[c]]-sum[lc[d]],mid=l+r>>1;
          if (t>=k) a=lc[a],b=lc[b],c=lc[c],d=lc[d],r=mid;
          else a=rc[a],b=rc[b],c=rc[c],d=rc[d],l=mid+1,k-=t;
    }
    return l;
}

int main()
{
    int n=read(),m=read(),i,x,y,ans=0,k;
    for (i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
    for (i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
    dfs(1),sort(b+1,b+n+1);
    for (i=2;i<=n;i++)
        if (b[tot]!=b[i]) b[++tot]=b[i];
    for(i=1;i<=n;i++) change(1,tot,a[pos[i]],root[i],root[id[pa[pos[i]][0]]]);
    for (i=1;i<=m;i++)
    {
        x=read(),y=read(),k=read(),x^=ans;
        printf("%d",ans=b[ask(x,y,k)]);
        if (i<m) printf("\n");
    }
    return 0;
}

题目大意：有5种运算维护集合S(S初始为空)并最终输出S。

　　5种运算如下：

U T S∪T

I T S∩T

D T S－T

C T T－S

S T S⊕T

　　基本集合运算如下：

A∪B
{x : xÎA or xÎB}

A∩B
{x : xÎA and xÎB}

A－B
{x : xÎA and xÏB}

A⊕B
(A－B)∪(B－A)

思路：：每个数之间加入一个数,就像这样2 2.5 3 3.5 4 [2,3) -> [2,2.5] (3,4] -> [3.5,4] 用01表示集合，则U 区间涂1；I 两侧区间涂0；D 区间涂0；C 两侧涂0,中间取反；S 区间取反。用线段树解决，标记的下传很重要（被坑了）。

代码：

#include<cstdio>
#include<iostream>
#define n 131073
using namespace std;

int lazy[n<<2],num[n<<2],rev[n<<2];

int read()
{
     int x=0,y=0;
     char ch=getchar();
     while (ch<'0' || ch>'9')
     {
           if (ch=='(') y=1;
           ch=getchar();
     }
     while (ch>='0' && ch<='9')
     {
           x=x*10+ch-48;
           ch=getchar();
     }
     if (ch==')') y=-1;
     return x*2+y+2;
}

void push_down(int x,int l,int r)
{
     int y=lazy[x],z=rev[x];
     lazy[x]=-1,rev[x]=0;
     if (l==r)
     {
          if (y!=-1) num[x]=y;
          num[x]^=z;
          return;
     }
     if (y!=-1)
     {
         lazy[x<<1]=lazy[x<<1|1]=y;
         rev[x<<1]=rev[x<<1|1]=0;
     }
     rev[x<<1]^=z,rev[x<<1|1]^=z;
}

void add(int L,int R,int l,int r,int cur,int val)
{
     if (l>r) return;
     push_down(cur,L,R);
     if (l<=L && r>=R)
     {
           if (val<2) lazy[cur]=val;
           else rev[cur]^=1;
           return;
     }
     int mid=L+R>>1;
     if (l>mid) add(mid+1,R,l,r,cur<<1|1,val);
     else if (r<=mid) add(L,mid,l,r,cur<<1,val);
          else add(L,mid,l,mid,cur<<1,val),add(mid+1,R,mid+1,r,cur<<1|1,val);
}

int ask(int l,int r,int x,int cur)
{
    push_down(cur,l,r);
    if (l==r) return num[cur];
    int mid=l+r>>1;
    if (x<=mid) return ask(l,mid,x,cur<<1);
    else return ask(mid+1,r,x,cur<<1|1);
}

int main()
{
    char ch[9];
    for (int i=0;i<=n*4;i++) lazy[i]=-1;
    while (scanf("%s",ch)!=EOF)
    {
          int a=read(),b=read();
          if (ch[0]=='U') add(1,n,a,b,1,1);
          if (ch[0]=='I') add(1,n,1,a-1,1,0),add(1,n,b+1,n,1,0);
          if (ch[0]=='D') add(1,n,a,b,1,0);
          if (ch[0]=='C') add(1,n,1,a-1,1,0),add(1,n,a,b,1,2),add(1,n,b+1,n,1,0);
          if (ch[0]=='S') add(1,n,a,b,1,2);
    }
    int h=0,t=0,flag=0;
    for (int i=1;i<=n;i++)
        if (ask(1,n,i,1))
        {
            if (!h) h=i;
            t=i;
        }
        else
        {
            if (h)
            {
                if (flag) printf(" ");
                else flag=1;
                if (h&1) printf("(");
                else printf("[");
                printf("%d,%d",h/2-1,(t+1)/2-1);
                if (t&1) printf(")");
                else printf("]");
            }
            h=t=0;
        }
    if (!flag) printf("empty set");
    else printf(" ");
    return 0;
}