线段树典型例题--poj2777

这到题我认为网上有些人的算法是不对的。

#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <algorithm>using namespace std;const int N=300000;int col[N];int n,m,t,sum;bool pp[N],ans[33];void down(int i){    if (!pp[i]) return;    col[i*2]=col[i*2+1]=col[i];    pp[i*2]=pp[i*2+1]=true;    pp[i]=false;}void update(int i){    col[i]=col[i*2]|col[i*2+1];}void ins(int i,int l,int r,int x,int y,int k){    if (x<=l && y>=r)    {        col[i]=1<<(k-1);        pp[i]=true;        return;    }    down(i);    int mid=(l+r)/2;    if (x<=mid) ins(i*2,l,mid,x,y,k);    if (y>mid) ins(i*2+1,mid+1,r,x,y,k);    update(i);}void find(int i,int l,int r,int x,int y){    if (x<=l && y>=r)    {        int tmp=col[i];        for (int p=1;p<=t;p++)        {            ans[p]|=tmp&1;            tmp>>=1;            if (tmp==0) break;        }        return;    }    down(i);    int mid=(l+r)/2;    if (x<=mid) find(i*2,l,mid,x,y);    if (y>mid) find(i*2+1,mid+1,r,x,y);    update(i);}void build(int i,int l,int r){    col[i]=1;    if (l==r) return;    int mid=(l+r)/2;    build(i*2,l,mid);    build(i*2+1,mid+1,r);}int main(){    int i,u,v,c;    char ch;    freopen("in","r",stdin);    scanf("%d%d%d\n",&n,&t,&m);    build(1,1,n);    while (m--)    {        scanf("%c",&ch);        if (ch=='P')        {            scanf("%d%d\n",&u,&v);            if (u>v) swap(u,v);            memset(ans,0,sizeof(ans));            find(1,1,n,u,v);            sum=0;            for (i=1;i<=t;i++)                sum+=ans[i];            printf("%d\n",sum);        }        else        {            scanf("%d%d%d\n",&u,&v,&c);            if (u>v) swap(u,v);            ins(1,1,n,u,v,c);        }    }}