Codeforces 121E Lucky Array
Luckyとつくけど悪問ではない。
問題をどう見てもsegment treeに見える。
「区間にk>=0を足す」「区間の定数cの数を数える」というクエリが必要で、これは「区間の最大値」と「区間の最大値の個数」を持っておけばよい。
しかしこの場合、求めたいものcが最大値でない場合があるので、最大値を超えたら適当な小さい値に変えておく。
これを行うことで、O(m log n)の操作を30個(Lucky numberの候補の数)のsegment treeの全部に行うことで解ける。
が、3*10^6に遅延評価segtreeの重いlogがつくので結構TLEが厳しい。なのでひたすら定数倍改善をする。
正解ソース(TLEするけど)は60分くらいで書きあがったんだけど、そこから定数倍改善に1.5h費やしてしまった...
せっかくなので改善前と改善後を両方載せておきます
before
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; #define SIZE 131072 int data[30]={4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777}; class segtree { public: int segmax[SIZE*2]; int segnum[SIZE*2]; int flag[SIZE*2]; int gval; void init() { for(int i=SIZE;i<SIZE*2;i++) { segmax[i]=0; segnum[i]=1; flag[i]=0; } for(int i=SIZE-1;i>=1;i--) { segnum[i]=segnum[i*2]+segnum[i*2+1]; } } void update(int beg,int end,int node,int lb,int ub,int num) { if(ub<beg||end<lb) { return; } if(beg<=lb&&ub<=end) { segmax[node]+=num; flag[node]+=num; return; } if(flag[node]) { segmax[node*2]+=flag[node]; segmax[node*2+1]+=flag[node]; flag[node*2]+=flag[node]; flag[node*2+1]+=flag[node]; flag[node]=0; } update(beg,end,node*2,lb,(lb+ub)/2,num); update(beg,end,node*2+1,(lb+ub)/2+1,ub,num); if(segmax[node*2]==segmax[node*2+1]) { segnum[node]=segnum[node*2]+segnum[node*2+1]; segmax[node]=segmax[node*2]; } else { if(segmax[node*2]>segmax[node*2+1]) { segnum[node]=segnum[node*2]; segmax[node]=segmax[node*2]; } else { segnum[node]=segnum[node*2+1]; segmax[node]=segmax[node*2+1]; } } } int get(int beg,int end,int node,int lb,int ub) { if(ub<beg||end<lb) { return 0; } if(beg<=lb&&ub<=end) { if(segmax[node]==gval) { return segnum[node]; } else { return 0; } } if(flag[node]) { segmax[node*2]+=flag[node]; segmax[node*2+1]+=flag[node]; flag[node*2]+=flag[node]; flag[node*2+1]+=flag[node]; flag[node]=0; } return get(beg,end,node*2,lb,(lb+ub)/2)+get(beg,end,node*2+1,(lb+ub)/2+1,ub); } int getidx(int node,int lb,int ub) { if(lb==ub) { return lb; } if(flag[node]) { segmax[node*2]+=flag[node]; segmax[node*2+1]+=flag[node]; flag[node*2]+=flag[node]; flag[node*2+1]+=flag[node]; flag[node]=0; } if(segmax[node*2]>gval) { return getidx(node*2,lb,(lb+ub)/2); } else { return getidx(node*2+1,(lb+ub)/2+1,ub); } } }; segtree tree[30]; int main() { int num,query; scanf("%d%d",&num,&query); for(int i=0;i<30;i++) { tree[i].gval=data[i]; tree[i].init(); } for(int i=0;i<num;i++) { int zan; scanf("%d",&zan); for(int j=0;j<30;j++) { tree[j].update(i,i,1,0,SIZE-1,zan); } } for(int p=0;p<query;p++) { string str; cin>>str; if(str=="add") { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); za--; zb--; for(int i=0;i<30;i++) { tree[i].update(za,zb,1,0,SIZE-1,zc); } } else { int za,zb; scanf("%d%d",&za,&zb); za--; zb--; int sum=0; for(int i=0;i<30;i++) { for(;;) { if(tree[i].segmax[1]<=tree[i].gval) { break; } int zan=tree[i].getidx(1,0,SIZE-1); tree[i].update(zan,zan,1,0,SIZE-1,-100000000); } sum+=tree[i].get(za,zb,1,0,SIZE-1); } printf("%d\n",sum); } } }
after
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; #define SIZE 131072 int data[30]={4,7,44,47,74,77,444,447,474,477,744,747,774,777,4444,4447,4474,4477,4744,4747,4774,4777,7444,7447,7474,7477,7744,7747,7774,7777}; class segtree { public: short segmax[SIZE*2]; int segnum[SIZE*2]; short flag[SIZE*2]; int gval; inline void init(vector<int>vec) { for(int i=0;i<vec.size();i++) { segmax[i+SIZE]=vec[i]; } for(int i=SIZE;i<SIZE*2;i++) { segnum[i]=1; } for(int i=SIZE-1;i>=1;i--) { int l=i+i,r=l+1; segmax[i]=max(segmax[l],segmax[r]); segnum[i]=segnum[l]*(segmax[i]==segmax[l])+segnum[r]*(segmax[i]==segmax[r]); } } inline void update(int beg,int end,int node,int lb,int ub,int num) { if(beg<=lb&&ub<=end) { segmax[node]+=num; flag[node]+=num; return; } int l=node+node,r=l+1; if(flag[node]) { segmax[l]+=flag[node]; segmax[r]+=flag[node]; flag[l]+=flag[node]; flag[r]+=flag[node]; flag[node]=0; } if(beg<=(lb+ub)/2) { update(beg,end,l,lb,(lb+ub)/2,num); } if(end>=(lb+ub)/2+1) { update(beg,end,r,(lb+ub)/2+1,ub,num); } segmax[node]=max(segmax[l],segmax[r]); segnum[node]=segnum[l]*(segmax[node]==segmax[l])+segnum[r]*(segmax[node]==segmax[r]); } inline int get(int beg,int end,int node,int lb,int ub) { if(ub<beg||end<lb||segmax[node]!=gval) { return 0; } if(beg<=lb&&ub<=end) { return segnum[node]; } int l=node+node,r=l+1; if(flag[node]) { segmax[l]+=flag[node]; segmax[r]+=flag[node]; flag[l]+=flag[node]; flag[r]+=flag[node]; flag[node]=0; } return get(beg,end,l,lb,(lb+ub)/2)+get(beg,end,r,(lb+ub)/2+1,ub); } inline void kill(int node) { if(node>=SIZE) { segmax[node]=-20000; return; } int l=node*2,r=node*2+1; if(flag[node]) { segmax[l]+=flag[node]; segmax[r]+=flag[node]; flag[l]+=flag[node]; flag[r]+=flag[node]; flag[node]=0; } if(segmax[l]>gval) { kill(l); } if(segmax[r]>gval) { kill(r); } segmax[node]=max(segmax[l],segmax[r]); segnum[node]=segnum[l]*(segmax[node]==segmax[l])+segnum[r]*(segmax[node]==segmax[r]); } }; segtree tree[30]; int main() { int num,query; scanf("%d%d",&num,&query); vector<int>vec; for(int i=0;i<num;i++) { int zan; scanf("%d",&zan); vec.push_back(zan); } for(int i=0;i<30;i++) { tree[i].gval=data[i]; tree[i].init(vec); } for(int p=0;p<query;p++) { char tp,gav; scanf(" %c",&tp); if(tp=='a') { int za,zb,zc; scanf("%c%c%d%d%d",&gav,&gav,&za,&zb,&zc); za--; zb--; for(int i=0;i<30;i++) { tree[i].update(za,zb,1,0,SIZE-1,zc); } } else { int za,zb; scanf("%c%c%c%c%d%d",&gav,&gav,&gav,&gav,&za,&zb); za--; zb--; int sum=0; for(int i=0;i<30;i++) { if(tree[i].segmax[1]>data[i]) { tree[i].kill(1); } sum+=tree[i].get(za,zb,1,0,SIZE-1); } printf("%d\n",sum); } } }
全然原型をとどめてない...
やったことは、ifを消したりいらない値を適当に処理するのをを一気にやったりcinを消したり掛け算を減らしたり関数呼び出しの回数を減らしたりget関数の自明な枝刈りをおこなったり。最後にintをshortに変えたら爆速になって通りました。
