HZOJ string

正解炸了……

考试的时候想到了正解，非常高兴的打出来了线段树，又调了好长时间，对拍了一下发现除了非常大的点跑的有点慢外其他还行。因为复杂度算着有点高……

最后正解死于常数太大……旁边的lyl用同样的算法拿了90分我却拿了个暴力的分40……花了那么多时间一分没多拿原地爆炸……

由于大部分时间押在了T1，然后考试就炸了……

题解：

因为字符串长度虽然很大，但是只有26个字符，考虑桶排，用线段树每个节点开一个26的桶，维护这个区间中各个数的个数，对于排序就可以拆成26次区间赋值。然而这样的down函数的复杂度是26，于是整个算法的复杂度就成了$nlog_n*26^2$,40分成功炸掉（加两个优化可以搞到60分），然后就有lyl及其没有素质地给他循环展开了,AC……

还是说正解吧，和‘花神游历各国’类似，线段树维护这一段的值，不一样则为0，本来以为这样会很慢，但是它会越来越快：每次排序最多增加2个块，但这种增加是有限制的，大部分情况下块是在减少，所以它会越来越快。由于此时的down是O1的，于是总复杂度$nlog_n*26$，成功A掉。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define MAXN 100010

 using namespace std;

 struct tree

 {

     int l,r,sum;

     #define l(x) tr[x].l

     #define r(x) tr[x].r

     #define ls(x) (x*2)

     #define rs(x) ((ls(x))+1)

     #define sum(x) tr[x].sum

 }tr[MAXN*];

 char a[MAXN];

 int n,m,yz[MAXN];

 void pushup(int x)

 {

     if(l(x)==r(x))return;

     sum(x)=(sum(ls(x))==sum(rs(x))?sum(ls(x)):);

 }

 void build(int l,int r,int x)

 {

     l(x)=l,r(x)=r;

     if(l==r){sum(x)=a[l];yz[l]=x;return;}

     int mid=(l+r)>>;

     build(l,mid,ls(x));

     build(mid+,r,rs(x));

     pushup(x);

 }

 void down(int x)

 {

     if(!sum(x))return;

     if(l(x)!=r(x))sum(ls(x))=sum(rs(x))=sum(x);

 }

 void add(int l,int r,int x,int data)

 {

     if((l(x)>=l&&r(x)<=r)||sum(x)==data)

     {sum(x)=data;down(x);return;}

     down(x);

     int mid=(l(x)+r(x))>>;

     if(l<=mid)add(l,r,ls(x),data);

     if(r>mid) add(l,r,rs(x),data);

     pushup(x);

 }

 int t[];

 void ask(int l,int r,int x)

 {

     down(x);

     if(l>r(x)||r<l(x))return;

     if(l<=l(x)&&r>=r(x)&&sum(x))

     {

         t[sum(x)]+=r(x)-l(x)+;

         return;

     }

     down(x);

     int mid=(l(x)+r(x))>>;

     if(l<=mid)ask(l,r,ls(x));

     if(r>mid) ask(l,r,rs(x));

 }

 void work(int x,int l,int r)

 {

     memset(t,,sizeof(t));

     ask(l,r,);

     int tl=l;

     if(x==)

     {

         for(register int i=;i<=;i++)

         if(t[i])

         {

             add(tl,tl+t[i]-,,i);

             tl=tl+t[i];

         }

     }

     else

     {

         for(register int i=;i>=;i--)

         if(t[i])

         {

             add(tl,tl+t[i]-,,i);

             tl=tl+t[i];

         }

     }

 }

 void dfs(int x)

 {

     down(x);

     if(l(x)==r(x))return;

     dfs(ls(x)),dfs(rs(x));

 }

 inline int read();

 signed main()

 {

 //    freopen("in.txt","r",stdin)    ;

     n=read(),m=read();

     char ooo=getchar();int len=;

     while(ooo<'a'||ooo>'z')ooo=getchar();

     while(ooo>='a'&&ooo<='z'){a[++len]=ooo-'a'+;ooo=getchar();}

     build(,n,);

     int x,l,r;

     for(register int i=;i<=m;++i)

     {

         l=read(),r=read(),x=read();

         work(x,l,r);

     }

     dfs();

     for(int i=;i<=n;i++)

         putchar(sum(yz[i])+'a'-);

     puts("");

 }

 inline int read()

 {

     int s=;char a=getchar();

     while(a<''||a>'')a=getchar();

     while(a>=''&&a<=''){s=s*+a-'';a=getchar();}

     return s;

 }

巴特西

HZOJ string

最新文章

热门文章