edward_mj

SGU155 笛卡尔树

题意：

给定N个二元组(Ki,Ai)

让你建立一棵笛卡尔树。

这个笛卡尔树实际上就是一个Treap.

k为二叉排序树的关键字，a为堆的关键字，堆是一个小根堆。

分析：

直接Treap会TLE,因为他给定了关键值，会退化成O(n^2)

然后我们可以根据Ki把结点从小到大排序，

然后每次都是最右边插入新的结点，

然后维护只需要左旋（他们叫右旋= =我觉得向左比较形象）

只有左旋的话我们可以注意到两个性质：

1、那么就是旋转以后，我这个结点不会增加新的儿子。

2、旋转以后，我必然是下一次插入的点的父结点。

别问我问什么。。。手画一下。。。证明这东西不是我这个级别做的事

然后我们可以注意到，从根开始连续向右到底这条路径可以看成一个栈！

每次左旋，就是一次出栈操作。

每次加结点，就是一次入栈操作。

于是，加结点和左旋操作数都<=n

所以，证明了这个算法的复杂度是：O(N)！

HINT

1A。

code：

#include #include #define N 60000
using namespace std;
struct re{int k,a,wz;}d[N];
struct trtype{int l,r,fa,zz;}tr[N];
int n,tot,mr,locate[N];

void left(int t){
    int p=tr[t].fa;
    tr[p].r=tr[t].l;
    tr[tr[t].l].fa=p;
    tr[t].l=p;
    tr[0].l=0; tr[0].r=0; tr[0].fa=0; tr[0].zz=0;
    if (tr[tr[p].fa].l==p) tr[tr[p].fa].l=t;
    if (tr[tr[p].fa].r==p) tr[tr[p].fa].r=t;
    tr[t].fa=tr[p].fa;
    tr[p].fa=t;
}

void work(){
    tot=1; mr=1; tr[1].l=0; tr[1].r=0; tr[1].fa=0; tr[1].zz=1;
    for (int i=2;i<=n;i++){
        tot++;
        tr[tot].l=0; tr[tot].r=0; tr[tot].zz=i; tr[tot].fa=mr; tr[mr].r=tot;
        mr=tot;
        int now=tot;
        while (tr[now].fa!=0 && d[tr[tr[now].fa].zz].a>d[i].a)
          left(now);
    }
}

inline int wz(int x){
return d[tr[x].zz].wz;
}

void print(){
    printf("YESn");
    for (int i=1;i<=tot;i++) locate[d[tr[i].zz].wz]=i;
    for (int i=1;i<=n;i++){
        int t=locate[i];
        printf("%d %d %dn",wz(tr[t].fa),wz(tr[t].l),wz(tr[t].r));
    }
}

bool cmp(re x,re y){
if (x.k return false;
}

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&d[i].k,&d[i].a);
        d[i].wz=i;
    }
    sort(&d[1],&d[n+1],cmp);
    work();
    print();
    return 0;
}

SPOJ 220 后缀数组分组思想

题意：

题目：https://www.spoj.pl/problems/PHRASES/

给定N个字符串，让你求一个最长的串，使得他满足：

在每个串中它都出现过>=两次，而且出现的位置不重叠。

分析：

就是构造后缀数组，然后二分答案，用分组思想，看能否实现。

HINT

一开始没看到不能重叠，WA了一遍。

code：

#include #include #include using namespace std;
const int N=111111;
char s[N];
struct gtp{int data[3],next;}g[N];
int cn,ls[N],color[N],e,n,sa[N],rank[N],a[N][3],G[N],hash[N],num[N],height[N],maxsa[N],minsa[N],list[N];

void init(){
     char inschar=’A’,ch;
     scanf("%dn",&cn);
     n=0;
     for (int i=1;i<=cn;i++){
         while (scanf("%c",&ch)!=EOF && ch!=’n’)
           if (ch>=’a’ && ch<='z'){
             s[++n]=ch;
             color[n]=i;
           }
         s[++n]=inschar++;
         color[n]=0;
     }
}

inline bool cmp(int x,int y){
if (s[x] return false;
}

inline void add(int x,int data[]){
       e++;
       g[e].next=ls[x]; ls[x]=e;
       memcpy(g[e].data,data,sizeof(a[0]));
}

void Jsort(){
     for (int k=1;k>=0;k–){
         e=0;
         memset(ls,0,sizeof(int)*(n+1));
         for (int i=n;i>=1;i–) add(a[i][k],a[i]);
         int tail=0;
         for (int i=0;i<=n;i++)
           for (int t=ls[i];t!=0;t=g[t].next)
             memcpy(a[++tail],g[t].data,sizeof(a[0]));
     }
}

void buildarr(){
     for (int i=1;i<=n;i++) sa[i]=i;
     sort(&sa[1],&sa[n+1],cmp);
     int tail=0;
     for (int i=1;i<=n;i++){
         if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
         rank[sa[i]]=tail;
     }
     for (int k=1;1<         int t=1<         for (int i=1;i<=n;i++){
             a[i][0]=rank[i];
             if (i+t<=n) a[i][1]=rank[i+t];
                    else a[i][1]=0;
             a[i][2]=i;
         }
         Jsort();
         tail=0;
         for (int i=1;i<=n;i++){
             if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
             rank[a[i][2]]=tail;
         }
     }
     for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void MakeHeight(){
     memset(height,0,sizeof(int)*(n+1));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st=max(height[rank[i-1]]-1,0),j=i+st,k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]) {j++;k++;st++;}
         height[rank[i]]=st;
     }
}

bool flag(int limit){
     int Gn=1; G[1]=1;
     for (int i=2;i<=n;i++)
       if (height[i]>=limit) G[i]=Gn;
                        else G[i]=++Gn;
     int j=1;
     for (int i=1;i<=Gn;i++){
         int st=j,total=0,tail=0;
         while (j<=n && G[j]==i) j++;
         for (int k=st;k           if (hash[color[sa[k]]]!=i){
             hash[color[sa[k]]]=i;
             num[color[sa[k]]]=1;
             minsa[color[sa[k]]]=sa[k];
             maxsa[color[sa[k]]]=sa[k];
             list[++tail]=color[sa[k]];
           }
           else{
             num[color[sa[k]]]++;
             minsa[color[sa[k]]]=min(minsa[color[sa[k]]],sa[k]);
             maxsa[color[sa[k]]]=max(maxsa[color[sa[k]]],sa[k]);
             if (num[color[sa[k]]]==2 && color[sa[k]]!=0) total++;
           }
         if (total!=cn) continue;
         bool ff=true;
         for (int k=1;k<=tail;k++)
           if (maxsa[k]-minsa[k]         if (ff) return true;
     }
     return false;
}

void binary(){
     int l=0,r=n,mid;
     while (l+1           mid=l+r>>1;
           if (flag(mid)) l=mid;
                     else r=mid-1;
     }
     if (flag(r)) printf("%dn",r);
             else printf("%dn",l);
}

int main(){
    int testcase;
    scanf("%d",&testcase);
    for (int i=1;i<=testcase;i++){
        init();
        buildarr();
        MakeHeight();
        binary();
    }
}

[USACO6.3.1 COWXOR] Trie 2进制分解

题目：

http://www.wzoi.org/usaco/16%5C107.asp

总的来说就是给定一个数列(n<=100000)。

求一段连续的子数列，使得其中的数都xor在一起以后，得到的值最大。

分析：

自己想的原创算法吖

首先我们先分析一下xor这个运算的性质。

易得y=y xor t xor t（即偶数次xor同一个数，结果和原来一样）

于是我们可以设s[i]表示从a[1]xor到a[i]的值。(定义s[0]=0)

如果我们需要某一段[i,j]的xor值，就可以这样求s[j] xor s[i-1]，因为a[1]到a[i-1]的数被xor了两次！

这样，问题转化为：求max(s[i] xor s[j])，其中i∈[0,j]，j∈[1,n]。

于是现在要求的是取两个数的xor值最大！

首先我们应该明白，对于一个数字，我们可以把它看成一个长度为20的字符串(题目给的a[i]<=2^21-1)！

那么我们怎么比较这些字符串的大小呢？

很明显，我们是从首位扫到末尾！

于是假设我们现在枚举j，即已经确定了s[j]，然后在[0,j]的范围类找一个s[i] xor s[j]最大。

因为是当成字符串，我们用Trie树来储存那些数字！

然后从首位开始：

1、如果我这个s[j]的这一位是0，那么另外一个配对最好是1，

因为这样xor会得到1。如果找不到那就只能到0那边去。

2、如果我这个s[j]的这一位是1，那么另外一个配对最好是0，

理由同上。

因为越前的位在大小上影响更大，所以我们这样就贪心的走一遍Trie树，

所得的结果就是和s[j]配对最大的s[i]。

然后统计每个j对应的最大值，输出结果即可。

HINT

UASCO给的空间比较小，用指针可以过，但静态空间的Trie就不能开到极限那么大，开小一点就能过。

code：

/*
ID:jie22221
TASK:cowxor
LANG:C++
*/
#include const int N=111111;
struct treetype{int l,r,dep;}T[5*N];
struct gtp{int x,y,next;}g[N];
int n,a[N],s[N],ans=-1,ansi=0,ansj=0,tot,root,e=0,ls[5*N];

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

void add(int &p,int x,int dep,int link){
     if (p==0){
       tot++;
       p=tot;
       T[p].l=0;
       T[p].r=0;
       T[p].dep=dep;
     }
     if (dep==-1){
       addedge(p,link);
       return;
     }
     if (((1<                     else add(T[p].l,x,dep-1,link);
}

void init(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
     for (int i=1;i<=n;i++){
         s[i]=s[i-1]^a[i];
         if (a[i]>ans){
           ans=a[i];
           ansi=i;
           ansj=i;
         }
         if (s[i]>ans){
           ans=s[i];
           ansi=1;
           ansj=i;
         }
     }
     tot=1;
     root=1;
     T[1].l=0;
     T[1].r=0;
     T[1].dep=22;
}

inline bool flag(int x,int y,int z){
       if (x>ans) return true;
       if (x       if (z       if (z>ansj) return false;
       if (z-y       return false;
}

void work(){
     add(root,s[1],22,1);
     for (int i=2;i<=n;i++){
         int p=root,now=0;
         for (int j=22;j>=0;j–)
           if ((s[i]|(1<               if (T[p].l!=0) {p=T[p].l; now|=1<                         else p=T[p].r;
             }
           else {
               if (T[p].r!=0) {p=T[p].r; now|=1<                         else p=T[p].l;
               }
           if (flag(now,g[ls[p]].y+1,i)){
              ans=now;
              ansi=g[ls[p]].y+1;
              ansj=i;
           }
         add(root,s[i],22,i);
     }
}

void print(){
printf("%d %d %dn",ans,ansi,ansj);
}

int main(){
    freopen("cowxor.in","r",stdin);
    freopen("cowxor.out","w",stdout);
    init();
    work();
    print();
    return 0;
}

POJ 3261 后缀数组分组思想

题意：

给出一个串，求这个串的最长的出现过至少k次的子串。出现的位置可以重叠。

分析：

用后缀数组先处理出height数组，然后二分答案，根据limit将height分组，使得每一组里任意串的lcp>=limit。

然后如果某一组的串的个数超过>=k，那么flag=true。

插曲：

基数排序时e没有设为0，WA了和RE了好多遍。

code：

#include

POJ 1743 后缀数组分组思想 Sparse_Table (RMQ) 男人8题

题意：

楼教主男人8题里的一题。

给出一串数，让你找出最长的两段不重合的连续差值相等的子串。

分析：

先令S[I]=A[I]-A[I-1]，然后问题转化为求S[I]的最长不重合重复子串。

先用后缀数组处理好S[I]，然后二分答案分组，如果某一组里的MAX(SA[I])-MIN(SA[J])>LIMIT，表示这组可以找到不重合的答案。

然后输出即可。

插曲：

有一个地方Gn打成n了。WA了N久。

code：

#include #include #define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
const int N=22222;
struct gtp{int x,data[3],next;}g[N];
int n,s[N],sa[N],rank[N],height[N],a[N][3],ls[N],e;
int G[N],pu[20][N],pd[20][N],tmp[N],lg[N];

void init(){
    for (int i=0;i    for (int i=1;i    n–;
    int t=0; lg[1]=0;
    for (int i=1;i<=n;i++)
      if (1<                else lg[i]=lg[i-1];
}

inline void add(int x,int data[]){
    e++;
    g[e].x=x; g[e].next=ls[x]; ls[x]=e;
    memcpy(g[e].data,data,sizeof(a[0]));
}

void Jsort(){
    for (int k=1;k>=0;k–){
        e=0;
        for (int i=0;i<=n;i++) ls[i]=0;
        for (int i=n;i>=1;i–) add(a[i][k],a[i]);
        int tail=0;
        for (int i=0;i<=n;i++)
          for (int t=ls[i];t!=0;t=g[t].next)
              memcpy(a[++tail],g[t].data,sizeof(a[0]));
    }
}

void Sort(int l,int r){
    if (l>=r) return;
    int i=l,j=r,mid=s[sa[l+r>>1]],temp;
    while (i        while (s[sa[i]]        while (s[sa[j]]>mid) j–;
        if (i<=j){
            temp=sa[i]; sa[i]=sa[j]; sa[j]=temp;
            i++; j–;
        }
    }
    Sort(l,j);
    Sort(i,r);
}

void build(){
    for (int i=1;i<=n;i++) sa[i]=i;
    Sort(1,n);
    int tail=0;
    for (int i=1;i<=n;i++){
        if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
        rank[sa[i]]=tail;
    }
    for (int k=1;1<        for (int i=1;i<=n;i++){
            a[i][0]=rank[i];
            if (i+(1<                          else a[i][1]=0;
            a[i][2]=i;
        }
        Jsort();
        tail=0;
        for (int i=1;i<=n;i++){
            if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
            rank[a[i][2]]=tail;
        }
    }
    for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void Sparse_Table(){
    for (int i=1;i<=n;i++) pu[0][i]=sa[i];
    for (int i=1;i<=n;i++) pd[0][i]=sa[i];
    for (int k=1;1<      for (int i=1;i+(1<        pu[k][i]=max(pu[k-1][i],pu[k-1][i+(1<        pd[k][i]=min(pd[k-1][i],pd[k-1][i+(1<      }
}

inline int Maxsa(int l,int r){
int t=lg[r-l+1];
return max(pu[t][l],pu[t][r-(1<}

inline int Minsa(int l,int r){
int t=lg[r-l+1];
return min(pd[t][l],pd[t][r-(1<}

void MakeHeight(){
    for (int i=0;i<=n;i++) height[i]=0;
    for (int i=1;i<=n;i++){
        if (rank[i]==1) continue;
        int st=max(height[rank[i-1]]-1,0),j=i+st,k=sa[rank[i]-1]+st;
        while (j<=n && k<=n && s[j]==s[k]){st++;j++;k++;}
        height[rank[i]]=st;
    }
}

bool flag(int limit){
    int Gn=1; G[1]=1;
    for (int i=2;i<=n;i++)
      if (height[i]>=limit) G[i]=Gn;
                       else G[i]=++Gn;
    int j=1;
    for (int i=1;i<=Gn;i++){
        int st=j;
        while (j<=n && G[j]==i) j++;
        int ed=j-1;
        if (Maxsa(st,ed)-Minsa(st,ed)>limit) return true;
    }
    return false;
}

int binary(){
    int l=0,r=n,mid;
    while (l+1        mid=l+r>>1;
        if (flag(mid)) l=mid;
                  else r=mid-1;
    }
    if (flag(r)) return r;
    return l;
}

int main(){
    while (scanf("%d",&n) && n!=0){
        init();
        build();
        Sparse_Table();
        MakeHeight();
        int ans=binary();
        if (ans<4) printf("0n");
              else printf("%dn",ans+1);
    }
}