标签存档：数据结构

[SGU187 Twist and whirl – want to cheat]【Splay】

【题目大意】

给定一个1~n的排列，每次操作会将[l,r]这个区间上的数翻转。问到最后，整个排列变成个什么样？

【算法分析】

就是Splay加个翻转操作啦。。。非常easy。用来增加自信心。。。。

属于被秒杀题类型。。。

【时间复杂度】O(m lg n)

【空间复杂度】O(n)

【其它】1Y。

【CODE】

#include

[POJ3764 The xor-longest Path]【异或运算】【Trie树】

【题目大意】给定一棵树，然后一条树的路径的权和定义为路径上边权全部xor之后得出的值

【算法分析】树的话。设d[x]为从根到x这条路径的权。那么两点间的路径权就是d[x] xor d[y]。（LCA到根部分被两次xor抵消啦），然后就转化为给定n个数，求d[x]^d[y]最大。这个就和USACO第6章那个cowxor一模一样啦。利用Trie树求解。

【时间复杂度】O(30*N)

【空间复杂度】O(30*N)

【其它】1Y。在lcc大神空间看到有这题，然后一看题目。。。Orz，再次见面的题目就成水题啦。。。睡前一水。

【CODE】

#include #include #include const int N=100005; struct edge{int y,w;edge *next;}g[N*2],*ls[N]; int n,e,tot; int d[N],L[N],v[N],ch[N*32][2];
void addedge(int x,int y,int w){       g[++e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];       g[++e].y=x; g[e].w=w; g[e].next=ls[y]; ls[y]=&g[e]; }
void init(){      int i,x,y,w;      for (e=i=0;i     for (i=1;i          scanf("%d%d%d",&x,&y,&w);           addedge(x,y,w);       } }
void bfs(){      int i,head=-1,tail=0;      for (i=0;i      v[0]=1; L[0]=d[0]=0;      while (head!=tail){             head++;            for (edge *t=ls[L[head]];t;t=t->next)              if (!v[t->y]){                 d[t->y]=d[L[head]]^t->w;                 v[t->y]=1;                 L[++tail]=t->y;               }       } }
void Insert(int x){      int s,p,t;      for (p=1,s=30;s>=0;s--){         t=( (1<       if (!ch[p][t]){           ch[p][t]=++tot;           ch[tot][0]=ch[tot][1]=0;         }         p=ch[p][t];       } }
int Get(int x){     int res=0,s,p,t;     for (p=1,s=30;s>=0;s--){        t=( (1<      if (ch[p][!t]) {p=ch[p][!t]; res|=!t<                else {p=ch[p][t];   res|= t<     }     return res^x; }
void work(){       tot=1;       ch[1][0]=ch[1][1]=0;       Insert(d[0]);      int i,ans=0,now;      for (i=1;i          now=Get(d[i]);          if (now>ans) ans=now;           Insert(d[i]);       }       printf("%dn",ans); }
int main(){     while (scanf("%d",&n)!=EOF){            init();            bfs();            work();      } }

[HDOJ3436 Queue-jumpers]【Splay练手】

【题目大意】

一开始给定n个人，他们按编号1..n地排好了。

有3个操作。

分别是：

Top x：把编号为x个人放到a[1]。然后a[1..x-1]的数都向后移一位。

Query x：返回编号为x个人现在在哪里位置。

Rank x：返回排名在x的这个人是编号是多少？

【算法分析】

我采用的是Splay来离线解决。

由于n高达10^8。所以不能完全模拟。

首先是把询问都读进来，然后对于Top和Query碰到的编号，开一个List取出来，排序并去重。

然后开始构建Splay。

对于在List中的编号，我们把他构建成一个结点。

然后对于List[i]和List[i-1]之间的间隙结点，我把它们都压缩成一个结点。（当然Size的计算方法就有点不同了。）

然后这样，Splay上最多有2*Q个点了。

对于Top操作，我们就相当于删掉这个点，再插入一次这个点。

对于Query，我们可以直接把这个点Splay到根，然后算他的左子树的Size，+1就是答案。

对于Rank，我们就像找第k个元素那样，找到那个对应位置，输出就行了。（就是压缩块有点不同而已）

【其它】

2TLE。写惯了SBT。。。那个父亲的域老是忘了维护，导致死循环了。

【CODE】

#include

#include

#include #define update(p) (Tr[p].Size=Tr[ch[p][0]].Size+Tr[ch[p][1]].Size+Tr[p].weight)
const int N=305555;

struct Splay_t{
       int root,tot,Lasttop;
       int ch[N][2],pre[N];
       struct Node{int St,Size,weight;}Tr[N];
      
       void init(){
            root=tot=1;
            Lasttop=2;
            ch[1][0]=ch[1][1]=0;
            Tr[0].Size=0;
            pre[1]=0;
       }
      
       void rotate(int x,int T){
            int y=pre[x];
            if (T){
              ch[y][0]=ch[x][1];
              ch[x][1]=y;
              pre[ch[y][0]]=y;
              pre[x]=pre[y];
              pre[y]=x;
            }
            else{
              ch[y][1]=ch[x][0];
              ch[x][0]=y;
              pre[ch[y][1]]=y;
              pre[x]=pre[y];
              pre[y]=x;
            }
            if (ch[pre[x]][0]==y) ch[pre[x]][0]=x;
                             else ch[pre[x]][1]=x;
            update(y);
            update(x);
       }
      
       void Splay(int x,int cut){
            if (x==cut) return;
            int y,z;
            while (pre[x]!=cut){
                  y=pre[x]; z=pre[y];
                  if (z==cut) rotate(x,ch[y][0]==x);
                  else
                  if (ch[z][0]==y)
                    if (ch[y][0]==x) {rotate(y,1); rotate(x,1);}
                                else {rotate(x,0); rotate(x,1);}
                  else
                    if (ch[y][1]==x) {rotate(y,0); rotate(x,0);}
                                else {rotate(x,1); rotate(x,0);}
            }
       }
      
       void Ins(int St,int weight){
            tot++;
            ch[tot][0]=ch[tot][1]=0;
            Tr[tot].St=St;
            Tr[tot].weight=Tr[tot].Size=weight;
            if (tot==2){
              ch[root][0]=2;
              pre[2]=root;
            }
            else{
              Splay(tot-1,root);
              ch[tot-1][1]=tot;
              update(tot-1);
              pre[tot]=tot-1;
            }
            Splay(tot,root);
       }
      
       void Top(int x){
            if (Lasttop==x) return;
            Splay(x,root);
            int p,q;
            q=x; p=ch[x][1];
            while (p){
                  q=p;
                  p=ch[p][0];
            }
            if (q==x){
              ch[1][0]=ch[x][0];
              pre[ch[x][0]]=1;
            }
            else{
              Splay(q,x);
              ch[q][0]=ch[x][0];
              pre[q]=1;
              pre[ch[x][0]]=q;
              ch[1][0]=q;
              update(q);
            }
            Splay(Lasttop,root);
            ch[Lasttop][0]=x;
            pre[x]=Lasttop;
            ch[x][0]=ch[x][1]=0;
            update(x);
            update(Lasttop);
            Lasttop=x;
       }      
      
       int Query(int x){
           Splay(x,root);
           return Tr[ch[x][0]].Size+1;
       }
      
       int rank(int x){
           int p,done=0;
           p=ch[root][0];
           while (1){
                 if (x<=Tr[ch[p][0]].Size+done)
                   p=ch[p][0];
                 else
                 if (x>Tr[ch[p][0]].Size+done+Tr[p].weight){
                   done+=Tr[ch[p][0]].Size+Tr[p].weight;
                   p=ch[p][1];
                 }
                 else break;
           }
           Splay(p,root);
           return x-Tr[ch[p][0]].Size+Tr[p].St-1;
       }
      
}Splay;
int n,Q,Lt;
int op[N],a[N],List[N],pos[N];

int cmp(const void *A,const void *B){return *((int*)A) – *((int*)B);}
void init(){
     int i,cnt;
     Lt=List[0]=0;
     char Str[100];
     scanf("%d%d",&n,&Q);
     for (i=1;i<=Q;i++){
         scanf("%s%d",Str,&a[i]);
         switch (Str[0]){
                case ‘T’:op[i]=1; break;
                case ‘Q’:op[i]=2; break;
                case ‘R’:op[i]=3; break;
         }
         if (op[i]!=3) List[++Lt]=a[i];
     }
     qsort(List+1,Lt,sizeof(int),cmp);
     for (i=1,cnt=0;i<=Lt;i++){
         cnt+=(!cnt || List[i]!=List[cnt]);
         List[cnt]=List[i];
     }
     Lt=cnt;
}

void pre_Insert(){
     int i;
     Splay.init();
     for (List[0]=0,i=1;i<=Lt;i++){
         if (List[i]-List[i-1]>1)
           Splay.Ins(List[i-1]+1,List[i]-List[i-1]-1);
         Splay.Ins(List[i],1);
         pos[i]=Splay.tot;
     }
}

int Find(int x){
    int l=1,r=Lt,mid;
    while (l          mid=(l+r)/2;
          if (x>List[mid]) l=mid+1;
                      else r=mid;
    }
    return pos[l];
}

void solve(){
     int i;
     for (i=1;i<=Q;i++)
       switch (op[i]){
              case 1:Splay.Top(Find(a[i])); break;
              case 2:printf("%dn",Splay.Query(Find(a[i]))); break;
              case 3:
                   if (a[i]>List[Lt]) printf("%dn",a[i]);
                                 else printf("%dn",Splay.rank(a[i]));
                   break;
       }
}

int main(){
    int Tc,i;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d:n",i);
        init();
        pre_Insert();
        solve();
    }
}

[Vijos1083 小白逛公园] 【线段树维护最大子段和】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1756
【算法分析】
就是线段树动态维护最大子段和。实际易错较难的就只是update函数和找ans部分。
注意维护Lmax,Rmax,ans,Sum这4个域即可。
【其它】
1Y。
MS是oimaster大神出的题。。。但据说是动态树= =。。。貌似不是这题？好像还有小白逛公园加强版。。。不过不知道哪里有得交。。。
【CODE】
#include #include #include const int N=505555;
int n,m,res,Follow;
int w[N];
struct Node{int l,r,Lmax,Rmax,ans,Sum;}Tr[N*3];

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
}

int max(int x,int y){return x>y?x:y;}

void update(int p){
Tr[p].Sum=Tr[p*2].Sum+Tr[p*2+1].Sum;
Tr[p].Lmax=max(Tr[p*2].Lmax,Tr[p*2].Sum+Tr[p*2+1].Lmax);
Tr[p].Rmax=max(Tr[p*2+1].Rmax,Tr[p*2+1].Sum+Tr[p*2].Rmax);
Tr[p].ans=max(Tr[p*2].ans,Tr[p*2+1].ans);
Tr[p].ans=max(Tr[p].ans,Tr[p*2].Rmax+Tr[p*2+1].Lmax);
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r;
if (l==r){
Tr[p].Lmax=Tr[p].Rmax=Tr[p].ans=Tr[p].Sum=w[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
update(p);
}

void Change(int p,int pos,int key){
if (Tr[p].l==Tr[p].r){
Tr[p].Lmax=Tr[p].Rmax=Tr[p].ans=Tr[p].Sum=key;
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (pos<=mid) Change(p*2,pos,key);
else Change(p*2+1,pos,key);
update(p);
}

void Get(int p,int l,int r){
if (l<=Tr[p].l && Tr[p].r<=r){
res=max(res,Tr[p].ans);
res=max(res,Tr[p].Lmax+Follow);
Follow=max(Tr[p].Rmax,Tr[p].Sum+Follow);
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (l<=mid) Get(p*2,l,r);
if (r> mid) Get(p*2+1,l,r);
}

void solve(){
int op,x,y,i;
for (i=1;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if (op==1){
res=-0x7FFFFFFF; Follow=0;
if (x>y){x^=y; y^=x; x^=y;}
Get(1,x,y);
printf("%dn",res);
}
else Change(1,x,y);
}
}

int main(){
init();
build(1,1,n);
solve();
}

[JSOI2008]星球大战starwar 【并差集】【逆序处理】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1015
【算法分析】
就是逆过来，把拆分变成合并，用并差集即可。
【其它】= =1RE。n<=2m我还以为是他搞错了压在一起。。。
【CODE】
#include #include #include using namespace std;
const int N=405555;
struct edge{int y;edge *next;}g[405555],*ls[N];
int n,m,ans,e,Qn;
int F[N],Num[N],Q[N],v[N],reply[N];

inline void addedge(int x,int y){
g[++e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

int GF(int k){
int res,i,tmp;
for (i=k;F[i]!=i;i=F[i]);
res=i;
for (i=k;F[i]!=i;tmp=F[i],F[i]=res,i=tmp);
return res;
}

int main(){
e=0;
memset(ls,0,sizeof(ls));
memset(v,0,sizeof(v));
int x,y,i;
scanf("%d%d",&n,&m);
for (i=0;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=0;i F[i]=i;
Num[i]=1;
}
scanf("%d",&Qn);
ans=n;
for (i=0;i scanf("%d",&Q[i]);
if (!v[Q[i]]) ans–;
v[Q[i]]++;
}
for (i=0;i for (edge *t=ls[i];t;t=t->next)
if (!v[t->y] && GF(i)!=GF(t->y)){
ans–;
x=F[i]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
reply[Qn]=ans;
for (i=Qn-1;i>=0;i–){
v[Q[i]]–;
if (!v[Q[i]]){
ans++;
for (edge *t=ls[Q[i]];t;t=t->next)
if (!v[t->y] && GF(Q[i])!=GF(t->y)){
ans–;
x=F[Q[i]]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
}
reply[i]=ans;
}
for (int i=0;i<=Qn;i++) printf("%dn",reply[i]);
}