标签存档：数据结构

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2105

【题目大意】

给定一个串，你可以对它进行修改插入删除等操作。

然后有一种询问操作，LCP(i,j)表示求S[i..n]和S[j..n]的最长公共前缀。

总操作数<=10^5

但是各种修改字符串的操作总数<=5000

10^5-5000=95000，几乎全是询问操作。。。

【算法分析】

众所周知、判断字符串是否相等可以利用hash来达到很高的正确率。

然后经过询问某牛，无符号整数爆了相当于Mod。有符号之间爆好像是未定义什么的。于是一般都是用无符号整数。

然后既然是相当于Mod，所以利用* + -的hash函数对于一个相同的字符串，无论计算的次序如何都是会相等的。

于是简单地把hash值定为S[1]*p^n+S[2]*p^(n-1)+S[3]*p^(n-2)….

p就随便取个素数什么的。比如13、131~

然后对于求LCP，有一个二分答案然后判断是否相同的想法。

那么，我们需要快速知道某个区间的hash值。

区间问题、比较经典的有ST表和线段树这种。

1、ST表，因为每次修改都要重建，所以我把这个想法抹杀了，实际上本题是CQF《New Lcp》里面的原题。就是利用ST表的思想。而且确实每次修改以后都以O(n)的复杂度重建。。。当然他论文后面还有个利用平衡常数的常数优化。

2、由于本题长短会变，所以用平衡树取代线段树。然后现在相当于维护一个线性表。所以Splay是比较好的选择。另外区间的处理上Splay也比较方便。

【结果】

一看题目就想到第二种算法。敲出来以后干脆地TLE了。

每次修改的时间复杂度是O(lg n)

每次询问的时间复杂度是O(lg^2 n)

本题的特殊性在于询问很多，修改很少。

而ST表的时间复杂度

修改O(n)

询问O(lg n)

然后我这沙茶就悲剧了= =。

其实如果把修改弄多一点，我觉得我这个算法还是理论上不错的。就是常数比较大。

【CODE】

Splay+hash=TLE

经对拍，该代码无误。当然hash本身是有概率出错的。

 http://xiudaima.appspot.com/code/detail/4405003

【题目大意】

给定一个有M(0

【算法分析】

由于数据范围很小，做法很多，这里只介绍一种较优秀的算法。

首先建立一个哈希表和一个队列。

哈希表用来判断该元素是否存在于储存器中。

而队列的先进先出的性质与题目要求刚好相符合。

对于每次输入，先在哈希表中查找，如果存在，那么什么也不用做，否则插入队列，如果队列超过了规定的长度，那么把队头元素出队即可。

【时间复杂度】

O(M+N+Max(a[i]))

【空间复杂度】

O(M+N+Max(a[i]))

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2006
【算法分析】
就是搞成前缀和数组以后写一个rmq。然后在外面套一个二叉堆每次取最大值。然后把取出的区间裂解成两半，去掉中间那个最小值元素，继续放进二叉堆里，这样就可以AC。
T_T时间排在第3名。前面两个都是JZP神牛。
【时间复杂度】O((n+m) lg (n+m))
【空间复杂度】O(n lg n + n+m)
【吐槽】
NOI的时候写得二分答案+平衡树被卡得只剩30分T_T。。。
现在高3一个月只能回一次家。。。本次是因为配眼镜为由请假回家，就找些题练练手= =，准备我巨重要的NOIP。
【CODE】
#include #include #include #include using namespace std;
typedef __int64 lld;
const int N=500005;
int n,m,low,high;
int a[N];
int lg[N];
int zz[19][N];
lld ST[19][N];

int Get(int l,int r){
int k=lg[r-l+1];
if (ST[k][l] else return zz[k][r-(1<}

struct Heap_t{
struct Node{int l,r,i;lld key;}Q[N+N];
int tot;

void up(int k){
while (k>1 && Q[k>>1].key swap(Q[k>>1],Q[k]);
k>>=1;
}
}

void down(int k){
int p;
while (k<<1<=tot){
p=k<<1;
if (p if (Q[p].key>Q[k].key){
swap(Q[p],Q[k]);
k=p;
}
else break;
}
}

void Insert(int l,int r,int i){
if (l>r) return;
tot++;
Q[tot].l=l; Q[tot].r=r; Q[tot].i=i; Q[tot].key=ST[0][i]-ST[0][Get(l,r)];
up(tot);
}

void Del(){
Node tmp=Q[1];
Q[1]=Q[tot–];
down(1);
int pos=Get(tmp.l,tmp.r);
Insert(tmp.l,pos-1,tmp.i);
Insert(pos+1,tmp.r,tmp.i);
}

void init(){
int i;
for (tot=0,i=1;i<=n;i++)
Insert(max(0,i-high),i-low,i);
}

void solve(){
lld ans=0;
while (m){
ans+=Q[1].key;
Del();
m–;
}
printf("%I64dn",ans);
}
}Heap;

void init(){
scanf("%d%d%d%d",&n,&m,&low,&high);
int k,s,i;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) {ST[0][i]=ST[0][i-1]+a[i]; zz[0][i]=i;}
for (k=1;1< s=1< for (i=0;i+s+s-1<=n;i++)
if (ST[k-1][i] ST[k][i]=ST[k-1][i];
zz[k][i]=zz[k-1][i];
}
else{
ST[k][i]=ST[k-1][i+s];
zz[k][i]=zz[k-1][i+s];
}
}
for (i=1,k=0;i<=n;i++)
lg[i]=k+=(i==(1<}

int main(){
init();
Heap.init();
Heap.solve();
}

【题目大意】

给定n个物品，第i个物品有三个属性Ai,Bi,Ci。然后把这个n个物品分别分到3个集合中（集合可以为空），使得A集合中的物品的Max{Ai}+B集合中的物品的Max{Bi}+C集合中物品的Max{Ci}最小。（空集算作0）

【算法分析】

HDOJ3552是只有两个属性，那么按Ai排序，然后枚举Max{Ai}。然后剩下的另一边的Max{Bi}加起来就是当前值。

然后对于本题。依然按Ai排序，仍然从大到小枚举Max{Ai}。然后对剩下的另一边维护上面那个问题。

显然，若存在Bi<=Bj Ci<=Cj，那么i这个物品就没用了。那么我们可以维护一个线性表，使得他关于Bi递增。同时，删掉多余的物品以后，关于Ci递减。那么很显然，我们取某一个物品截开，那么这边取的值就是Bi+C_i+1，然后这种动态线性表显然就可以用平衡树维护。然后为了比较方便找前驱和后继，我用了Splay。

【其它】1Y。这次把Splay函数和rotate函数压了代码，Splay只有两个rotate，rotate里不用分类讨论。

【CODE】

#include

#include

#include

#include

#include

using namespace std;

const int N=105555;

const int INF=1000000000;

int n,root;

struct Node{int x,y,z;}a[N];

int pre[N],best[N],w[N],ch[N][2];

bool cmp(const Node &A,const Node &B){

     return A.x

}

void init(){

     int i;

     scanf("%d",&n);

     for (i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

     sort(a+1,a+n+1,cmp);

     memset(ch,0,sizeof(ch));

     memset(pre,0,sizeof(pre));

     root=n+1;

     ch[n+1][0]=n+2;

     pre[n+2]=n+1;

    

     a[n+1].y=INF; a[n+1].z=0;

     a[n+2].y= 0; a[n+2].z=INF;

    

     w[n+1]=INF; best[n+1]=0;

     w[n+2]=best[n+2]=0;

}

void update(int x){

     best[x]=INF;

     if (ch[x][0]) best[x]=min(best[ch[x][0]],best[x]);

     if (ch[x][1]) best[x]=min(best[ch[x][1]],best[x]);

     best[x]=min(w[x],best[x]);

}

void rotate(int x,int T){

     int y=pre[x];

     ch[y][!T]=ch[x][T];

     ch[x][T]=y;

     pre[x]=pre[y];

     pre[y]=x;

     pre[ch[y][!T]]=y;

     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 goal){

     int y,z;

     if (x==0 || x==goal) return;

     if (goal==0) root=x;

     while (pre[x]!=goal){

           y=pre[x]; z=pre[y];

           if (z!=goal) rotate(ch[z][0]==y^ch[y][0]==x?x:y,ch[y][0]==x);

           rotate(x,ch[pre[x]][0]==x);

     }

}

void Get_next(){

     int p=ch[root][1],q=root;

     while (p){

           q=p;

           p=ch[p][0];

     }

     Splay(q,0);

}

void Get_pre(){

     int p=ch[root][0],q=root;

     while (p){

           q=p;

           p=ch[p][1];

     }

     Splay(q,0);

}

bool Can_Insert(int i){

     int p=root,q;

     while (p){

           q=p;

           p=ch[p][a[p].y

     }

     Splay(q,0);

     if (a[q].y

     if (a[root].y>=a[i].y && a[root].z>=a[i].z) return false;

                                            else return true;

}

void (){

     int p=ch[root][0];

     while (ch[p][1]) p=ch[p][1];

     Splay(p,root);

     ch[p][1]=ch[root][1];

     pre[ch[root][1]]=p;

     pre[p]=0;

     root=p;

}

void Delete_Useless_Node(int i){

     while (1){

       if (a[root].y>a[i].y) Get_pre();

       if (a[root].y<=a[i].y && a[root].z<=a[i].z)

         ();

       else

         break;

     }

}

void Insert(int i){

     int p=root,q;

     while (p){

           q=p;

           p=ch[p][a[p].y

     }

     pre[i]=q;

     ch[q][a[q].y

     Splay(i,0);

     p=ch[i][1];

     while (ch[p][0]) p=ch[p][0];

     w[i]=a[i].y+a[p].z;

     Splay(p,i);

     update(i);

     Get_pre();

     w[root]=a[root].y+a[i].z;

     update(root);

}

void Try_Insert(int i){

     if (!Can_Insert(i)) return;

     Delete_Useless_Node(i);

     Insert(i);

}

    

void work(){

     int i,ans=INF,now;

     a[0].x=0;

     for (i=n;i>=0;i–){

         now=a[i].x;

         now+=best[root];

         if (now

         Try_Insert(i);

     }

     printf("%dn",ans);

}

int main(){

    init();

    work();

    return 0;

}

【题目连接】http://acm.hust.edu.cn/thx/problem.php?id=1407 （中文题目）

【算法分析】

这是一个好题。

首先有一个通用解法，平衡树+线段树，不过几乎肯定超时。（在线算法）

然后我YY到一个很经典的东西。P[j]-P[i-1]就得到i..j的信息。

于是对于一个询问，Q i j w。其实我们只要知道w在前j-1个位置有多少个，和w在前i个位置有多少个。就能通过一个减法得到答案。

然后我们把我们需要的信息抽出来。只维护他们。

每个信息的结构如下。{int Num,pos,key;}。其中Num表示询问的w。pos表示前pos个位置。key表示前pos个位置，Num出现几次？

然后我们观察假如change了一个数a[i]=p -> a[i]=w，该变的是哪些信息？

第一类，删除旧信息。对于所有Num=p，且pos>=i的信息，我们将他的key–

第二类，增加新信息。对于所有Num=w，且pos>=i的信息，我们将他的key++

好了。这里面我们需要的东西就显而易见了。

把信息按Num为第一关键字，pos为第二关键字排序，然后可以很容易用树状数组 or 线段树维护起来。

当然，我们当前位置+1。后面Num>w的是没有必要减回来的。因为我们最后是通过减法运算嘛。会互相抵消的。

【其它】

Orz。再删除了一次冗余的东西以后。排到了第一。

1 48386(2) edward_mj 4560 KB 1432 MS C++ 2382 B 2010-07-29 15:53:57 2 47267 lshmouse 6144 KB 1568 MS C++ 2727 B 2010-07-26 21:30:03 3 48114 foreverlin 5480 KB 1804 MS C++ 4771 B 2010-07-29 01:32:38 4 48102 WhatIsGenius 8548 KB 3128 MS C++ 1965 B 2010-07-28 23:09:53

【CODE】

#include #include #include #include #include using namespace std;
const int N=105555;
int n,m,tot;
int a[N];
struct Qu_t{int op,x,y,z;}Query[N];
struct List_t{int Num,pos;}L[N*2];
int Tr[N*2];

void init(){
     tot=0;
     scanf("%d%d",&n,&m);
     int i;
     for (i=1;i<=n;i++)
       scanf("%d",&a[i]);
     char tmp[10];
     for (i=1;i<=m;i++){
         scanf("%s",tmp);
         if (tmp[0]==’Q’){
           Query[i].op=0;
           scanf("%d%d%d",&Query[i].x,&Query[i].y,&Query[i].z);
           L[++tot].Num=Query[i].z; L[tot].pos=Query[i].y;
           L[++tot].Num=Query[i].z; L[tot].pos=Query[i].x-1;
         }
         else{
           Query[i].op=1;
           scanf("%d%d",&Query[i].x,&Query[i].y);
         }
     }
}

inline bool cmp(List_t A,List_t B){
     if (A.Num!=B.Num) return A.Num     return A.pos}

inline void Add(int k,int x){
     for (;k<=tot;k+=k&-k) Tr[k]+=x;
}

inline int Get_Sum(int k){
    int res=0;
    for (;k>0;k-=k&-k) res+=Tr[k];
    return res;
}

inline int Find(int key,int pos){
    int l=1,r=tot,mid;
    while (l      mid=(l+r)>>1;
      if (L[mid].Num                                                          else r=mid;
    }
    return l;
}

void pre_do(){
     sort(L+1,L+tot+1,cmp);
     int tmp=tot,i,x;
     tot=0;
     for (i=1;i<=tmp;i++){
         tot+=(i==1 || L[i].Num!=L[i-1].Num || L[i].pos!=L[i-1].pos);
         L[tot]=L[i];
     }
     for (i=1;i<=tot;i++) Tr[i]=0;
     for (i=1;i<=n;i++){
         x=Find(a[i],i);
         if (L[x].Num==a[i] && L[x].pos>=i) Add(x,1);
     }
}

void solve(){
     int i,j,x,y;
     for (i=1;i<=m;i++)
       if (Query[i].op==0){
         x=Get_Sum( Find ( Query[i].z,Query[i].y ) );
         y=Get_Sum( Find ( Query[i].z,Query[i].x-1 ) );
         printf("%dn",x-y);
       }
       else{
         x=Find(a[Query[i].x],Query[i].x);
         if (L[x].Num==a[Query[i].x] && L[x].pos>=Query[i].x) Add(x,-1);
        
         a[Query[i].x]=Query[i].y;
        
         x=Find(a[Query[i].x],Query[i].x);
         if (L[x].Num==a[Query[i].x] && L[x].pos>=Query[i].x) Add(x,1);
       }
}

int main(){
    init();
    pre_do();
    solve();
}