制作网站合同需注意,好的做蛋糕网站,宝安做棋牌网站建设多少钱,市场营销分析案例正解炸了…… 考试的时候想到了正解#xff0c;非常高兴的打出来了线段树#xff0c;又调了好长时间#xff0c;对拍了一下发现除了非常大的点跑的有点慢外其他还行。因为复杂度算着有点高…… 最后正解死于常数太大……旁边的lyl用同样的算法拿了90分我却拿了个暴力的分40…… 正解炸了…… 考试的时候想到了正解非常高兴的打出来了线段树又调了好长时间对拍了一下发现除了非常大的点跑的有点慢外其他还行。因为复杂度算着有点高…… 最后正解死于常数太大……旁边的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掉。 1 #includeiostream2 #includecstring3 #includecstdio4 #define MAXN 1000105 using namespace std;6 struct tree7 { 8 int l,r,sum;9 #define l(x) tr[x].l10 #define r(x) tr[x].r11 #define ls(x) (x*2)12 #define rs(x) ((ls(x))1)13 #define sum(x) tr[x].sum14 }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(lr){sum(x)a[l];yz[l]x;return;}26 int mid(lr)1;27 build(l,mid,ls(x));28 build(mid1,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)lr(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(lmid)add(l,r,ls(x),data);43 if(rmid) 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(lr(x)||rl(x))return;51 if(ll(x)rr(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(lmid)ask(l,r,ls(x));59 if(rmid) 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 tll;66 if(x1)67 {68 for(register int i1;i26;i)69 if(t[i])70 {71 add(tl,tlt[i]-1,1,i);72 tltlt[i];73 }74 }75 else 76 {77 for(register int i26;i1;i--)78 if(t[i])79 {80 add(tl,tlt[i]-1,1,i);81 tltlt[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 nread(),mread(); 97 char ooogetchar();int len0;98 while(oooa||oooz)ooogetchar(); 99 while(oooaoooz){a[len]ooo-a1;ooogetchar();}
100 build(1,n,1);
101 int x,l,r;
102 for(register int i1;im;i)
103 {
104 lread(),rread(),xread();
105 work(x,l,r);
106 }
107 dfs(1);
108 for(int i1;in;i)
109 putchar(sum(yz[i])a-1);
110 puts();
111 }
112 inline int read()
113 {
114 int s0;char agetchar();
115 while(a0||a9)agetchar();
116 while(a0a9){ss*10a-0;agetchar();}
117 return s;
118 } View Code 转载于:https://www.cnblogs.com/Al-Ca/p/11286365.html
