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掉。

 

HZOJ string
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #define MAXN 100010
  5 using namespace std;
  6 struct tree
  7 {    
  8     int l,r,sum;
  9     #define l(x) tr[x].l
 10     #define r(x) tr[x].r
 11     #define ls(x) (x*2)
 12     #define rs(x) ((ls(x))+1)
 13     #define sum(x) tr[x].sum
 14 }tr[MAXN*100];
 15 char a[MAXN];
 16 int n,m,yz[MAXN];
 17 void pushup(int x)
 18 {
 19     if(l(x)==r(x))return;
 20     sum(x)=(sum(ls(x))==sum(rs(x))?sum(ls(x)):0);
 21 }
 22 void build(int l,int r,int x)
 23 {
 24     l(x)=l,r(x)=r;
 25     if(l==r){sum(x)=a[l];yz[l]=x;return;}
 26     int mid=(l+r)>>1;
 27     build(l,mid,ls(x));
 28     build(mid+1,r,rs(x));
 29     pushup(x);
 30 }
 31 void down(int x)
 32 {
 33     if(!sum(x))return;
 34     if(l(x)!=r(x))sum(ls(x))=sum(rs(x))=sum(x);
 35 }
 36 void add(int l,int r,int x,int data)
 37 {
 38     if((l(x)>=l&&r(x)<=r)||sum(x)==data)
 39     {sum(x)=data;down(x);return;}    
 40     down(x);
 41     int mid=(l(x)+r(x))>>1;
 42     if(l<=mid)add(l,r,ls(x),data);
 43     if(r>mid) add(l,r,rs(x),data);
 44     pushup(x);
 45 }
 46 int t[27];
 47 void ask(int l,int r,int x)
 48 {
 49     down(x);
 50     if(l>r(x)||r<l(x))return;
 51     if(l<=l(x)&&r>=r(x)&&sum(x))
 52     {
 53         t[sum(x)]+=r(x)-l(x)+1;
 54         return;
 55     }
 56     down(x);
 57     int mid=(l(x)+r(x))>>1;
 58     if(l<=mid)ask(l,r,ls(x));
 59     if(r>mid) ask(l,r,rs(x));
 60 }
 61 void work(int x,int l,int r)
 62 {
 63     memset(t,0,sizeof(t));
 64     ask(l,r,1);
 65     int tl=l;
 66     if(x==1)
 67     {
 68         for(register int i=1;i<=26;i++)
 69         if(t[i])
 70         {
 71             add(tl,tl+t[i]-1,1,i);
 72             tl=tl+t[i];
 73         }
 74     }
 75     else 
 76     {
 77         for(register int i=26;i>=1;i--)
 78         if(t[i])
 79         {
 80             add(tl,tl+t[i]-1,1,i);
 81             tl=tl+t[i];
 82         }
 83     }    
 84 }
 85 void dfs(int x)
 86 {
 87     down(x);
 88     if(l(x)==r(x))return;
 89     dfs(ls(x)),dfs(rs(x));
 90 }
 91 inline int read();
 92 signed main()
 93 {
 94 //    freopen("in.txt","r",stdin)    ;
 95 
 96     n=read(),m=read();    
 97     char ooo=getchar();int len=0;
 98     while(ooo<'a'||ooo>'z')ooo=getchar();    
 99     while(ooo>='a'&&ooo<='z'){a[++len]=ooo-'a'+1;ooo=getchar();}
100     build(1,n,1);
101     int x,l,r;
102     for(register int i=1;i<=m;++i)
103     {
104         l=read(),r=read(),x=read();
105         work(x,l,r);    
106     }
107     dfs(1);
108     for(int i=1;i<=n;i++)    
109         putchar(sum(yz[i])+'a'-1);
110     puts("");
111 }
112 inline int read()
113 {
114     int s=0;char a=getchar();
115     while(a<'0'||a>'9')a=getchar();
116     while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
117     return s;
118 }
View Code

 

上一篇:最*周接收,不收费!这本过4分的SCI,国人占比64%!


下一篇:LINUX学习------2.3 Linux中的日志管理