codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1515.md (17666B)


      1 Source: https://codeforces.com/blog/entry/90236
      2 
      3 [1515A - Phoenix and Gold](/contest/1515/problem/A "Codeforces Global Round 14")
      4 
      5 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 using namespace std;
     16 
     17 void solve(){
     18   int n,x;
     19   int w[101];
     20   cin>>n>>x;
     21   int sum=0;
     22   for (int i=0;i<n;i++){
     23     cin>>w[i];
     24     sum+=w[i];
     25   }
     26   //if the sum is x, we cannot avoid the explosion
     27   if (sum==x){
     28     cout<<"NO"<<endl;
     29     return;
     30   }
     31   cout<<"YES"<<endl;
     32   //otherwise, the answer always exists
     33   //we will keep adding elements from left to right
     34   //if we can't add element i, we add element i+1 first by swapping the two
     35   for (int i=0;i<n;i++){
     36     if (x==w[i]){
     37       //i+1 will always be less than n because otherwise, the total sum would be x
     38       swap(w[i],w[i+1]);
     39     }
     40     cout<<w[i]<<' ';
     41     x-=w[i];
     42   }
     43   cout<<endl;
     44   return;
     45 }
     46 
     47 int main(){
     48   int T; cin>>T;
     49   while (T--)
     50     solve();
     51   return 0;
     52 }
     53 ```
     54 
     55 [1515B - Phoenix and Puzzle](/contest/1515/problem/B "Codeforces Global Round 14")
     56 
     57 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
     58 
     59 **Tutorial**
     60 
     61 Tutorial is loading...
     62 
     63 **Solution**
     64 
     65 ```
     66 #include <bits/stdc++.h>
     67 using namespace std;
     68 
     69 bool isSquare(int x){
     70   int y=sqrt(x);
     71   return y*y==x;
     72 }
     73 
     74 void solve(){
     75   int n;
     76   cin>>n;
     77   if (n%2==0 && isSquare(n/2))
     78     cout<<"YES"<<endl;
     79   else if (n%4==0 && isSquare(n/4))
     80     cout<<"YES"<<endl;
     81   else
     82     cout<<"NO"<<endl;
     83 }
     84 
     85 int main(){
     86   int t; cin>>t;
     87   while (t--)
     88     solve();
     89 }
     90 ```
     91 
     92 [1515C - Phoenix and Towers](/contest/1515/problem/C "Codeforces Global Round 14")
     93 
     94 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105 
    106 int N,M,X;
    107 int H[100001];
    108 
    109 void solve(){
    110   cin>>N>>M>>X;
    111   cout<<"YES"<<endl;
    112   set<pair<int,int>>s; //stores pairs of (height, index)
    113   for (int i=1;i<=M;i++)
    114     s.insert({0,i});
    115   for (int i=0;i<N;i++){
    116     cin>>H[i];
    117     pair<int,int>p=*s.begin();
    118     s.erase(p);
    119     cout<<p.second<<' ';
    120     s.insert({p.first+H[i],p.second});
    121   }
    122   cout<<endl;
    123 }
    124 
    125 int main(){
    126   int T; cin>>T;
    127   while (T--)
    128     solve();
    129 }
    130 ```
    131 
    132 [1515D - Phoenix and Socks](/contest/1515/problem/D "Codeforces Global Round 14")
    133 
    134 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
    135 
    136 **Tutorial**
    137 
    138 Tutorial is loading...
    139 
    140 **Solution**
    141 
    142 ```
    143 #include <bits/stdc++.h>
    144 using namespace std;
    145 
    146 int N,L,R;
    147 int C[200001];
    148 int lcnt[200001],rcnt[200001];
    149 
    150 void solve(){
    151   cin>>N>>L>>R;
    152   for (int i=1;i<=N;i++){
    153     lcnt[i]=0;
    154     rcnt[i]=0;
    155   }
    156   for (int i=1;i<=N;i++){
    157     cin>>C[i];
    158     if (i<=L)
    159       lcnt[C[i]]++;
    160     else
    161       rcnt[C[i]]++;
    162   }
    163   //remove pairs that are already matching
    164   for (int i=1;i<=N;i++){
    165     int mn=min(lcnt[i],rcnt[i]);
    166     lcnt[i]-=mn;
    167     rcnt[i]-=mn;
    168     L-=mn;
    169     R-=mn;
    170   }
    171   if (L<R){
    172     swap(lcnt,rcnt);
    173     swap(L,R);
    174   }
    175   //now, there are at least as many left socks as right socks
    176   int ans=0;
    177   for (int i=1;i<=N;i++){
    178     int extra=L-R; //always even
    179     int canDo=lcnt[i]/2;
    180     int Do=min(canDo*2,extra);
    181     //turn "Do"/2 left socks of color i into right socks
    182     ans+=Do/2;
    183     L-=Do;
    184   }
    185   //turn extra lefts into rights, then adjust all colors
    186   ans+=(L-R)/2+(L+R)/2;
    187   cout<<ans<<endl;
    188 }
    189 int main()
    190 {
    191   ios_base::sync_with_stdio(0);cin.tie(0);
    192   int T; cin>>T;
    193   while (T--)
    194     solve();
    195   return 0;
    196 }
    197 ```
    198 
    199 [1515E - Phoenix and Computers](/contest/1515/problem/E "Codeforces Global Round 14")
    200 
    201 Idea: [FieryPhoenix](/profile/FieryPhoenix "Master FieryPhoenix")
    202 
    203 **Tutorial**
    204 
    205 Tutorial is loading...
    206 
    207 **Solution**
    208 
    209 ```
    210 #include <bits/stdc++.h>
    211 using namespace std;
    212 typedef long long ll;
    213 ll MOD;
    214 
    215 int N;
    216 ll dp[405][405];
    217 
    218 ll fastexp(ll b, ll exp){
    219   if (exp==0)
    220     return 1;
    221   ll temp=fastexp(b,exp/2);
    222   temp=(temp*temp)%MOD;
    223   if (exp%2==1)
    224     temp*=b;
    225   return temp%MOD;
    226 }
    227 
    228 ll fact[405],inv[405],choose[405][405],pow2[405];
    229 
    230 void precompute(){
    231   fact[0]=1;
    232   inv[0]=1;
    233   for (int i=1;i<=N;i++){
    234     fact[i]=(fact[i-1]*i)%MOD;
    235     inv[i]=fastexp(fact[i],MOD-2);
    236   }
    237   for (int i=0;i<=N;i++)
    238     for (int j=0;j<=i;j++)
    239       choose[i][j]=((fact[i]*inv[j])%MOD*inv[i-j])%MOD;
    240   for (int i=0;i<=N;i++)
    241     pow2[i]=fastexp(2,i);
    242 }
    243 
    244 int main()
    245 {
    246   cin>>N>>MOD;
    247   precompute();
    248   dp[0][0]=1;
    249   for (int i=0;i<N;i++){
    250     for (int j=0;j<=i;j++){
    251       for (int k=1;i+k<=N;k++){
    252 	dp[i+k+1][j+k]+=((dp[i][j]*pow2[k-1])%MOD*choose[j+k][k]);
    253 	dp[i+k+1][j+k]%=MOD;
    254       }
    255     }
    256   }
    257   ll ans=0;
    258   for (int i=0;i<=N;i++)
    259     ans=(ans+dp[N+1][i])%MOD;
    260   cout<<ans<<endl;
    261   return 0;
    262 }
    263 ```
    264 
    265 [1515F - Phoenix and Earthquake](/contest/1515/problem/F "Codeforces Global Round 14")
    266 
    267 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
    268 
    269 **Tutorial**
    270 
    271 Tutorial is loading...
    272 
    273 **Solution**
    274 
    275 ```
    276 // Fix a spanning tree
    277 // Pick a leaf, either merge it into its parent or postpone it to the end
    278 #include <cstdio>
    279 #include <vector>
    280 #include <algorithm>
    281 
    282 const int MAXV=300005;
    283 const int MAXE=300005;
    284 
    285 int N,M,X;
    286 long long as[MAXV];
    287 
    288 int elist[MAXE*2];
    289 int head[MAXV];
    290 int prev[MAXE*2];
    291 int tot=0;
    292 
    293 bool vis[MAXV];
    294 
    295 int ans[MAXV];
    296 int front,back;
    297 
    298 void dfs(int u){
    299   vis[u]=true;
    300   for(int e=head[u];e!=-1;e=prev[e]){
    301     int v=elist[e^1];
    302     if(vis[v]) continue;
    303     dfs(v);
    304     if(as[u]+as[v]>=X){
    305       as[u]+=as[v]-X;
    306       ans[front++]=e>>1;
    307     }else{
    308       ans[--back]=e>>1;
    309     }
    310   }
    311 }
    312 
    313 int main(){
    314   scanf("%d %d %d",&N,&M,&X);
    315   long long total=0;
    316   for(int i=0;i<N;i++){
    317     scanf("%lld",&as[i]);
    318     total+=as[i];
    319   }
    320   if(total<1LL*(N-1)*X){
    321     printf("NO\n");
    322     return 0;
    323   }
    324   std::fill(head,head+N,-1);
    325   for(int i=0;i<M*2;i++){
    326     int U;
    327     scanf("%d",&U);
    328     U--;
    329     prev[i]=head[U];
    330     head[U]=i;
    331     elist[i]=U;
    332   }
    333   back=N-1;
    334   dfs(0);
    335   printf("YES\n");
    336   for(int i=0;i<N-1;i++){
    337     printf("%d\n",ans[i]+1);
    338   }
    339 }
    340 ```
    341 
    342 [1515G - Phoenix and Odometers](/contest/1515/problem/G "Codeforces Global Round 14")
    343 
    344 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
    345 
    346 **Tutorial**
    347 
    348 Tutorial is loading...
    349 
    350 **Solution**
    351 
    352 ```
    353 #include <cstdio>
    354 #include <vector>
    355 #include <cassert>
    356 #include <algorithm>
    357 #include <cmath>
    358 
    359 using ll = long long;
    360 
    361 std::vector<std::pair<int,int> > fwd[200005];
    362 std::vector<std::pair<int,int> > rev[200005];
    363 
    364 int vis[200005];
    365 int cc[200005];
    366 ll offset[200005];
    367 int ncc;
    368 ll loop[200005];
    369 std::vector<int> ord;
    370 
    371 ll gcd(ll a,ll b){
    372   return b?gcd(b,a%b):a;
    373 }
    374 
    375 void dfs_fwd(int x){
    376   vis[x]=1;
    377   for(auto e:fwd[x]){
    378     int y=e.first;
    379     if(vis[y]!=1){
    380       dfs_fwd(y);
    381     }
    382   }
    383   ord.push_back(x);
    384 }
    385 
    386 void dfs_rev(int x){
    387   vis[x]=2;
    388   for(auto e:rev[x]){
    389     int y=e.first,l=e.second;
    390     if(vis[y]!=2){
    391       cc[y]=cc[x];
    392       offset[y]=offset[x]+l;
    393       dfs_rev(y);
    394     }else if(cc[y]==cc[x]){
    395       loop[cc[x]]=gcd(loop[cc[x]],std::llabs(offset[x]+l-offset[y]));
    396     }
    397   }
    398 }
    399 
    400 int main(){
    401   int N,M;
    402   scanf("%d %d",&N,&M);
    403   for(int i=0;i<M;i++){
    404     int A,B,L;
    405     scanf("%d %d %d",&A,&B,&L);
    406     A--,B--;
    407     fwd[A].push_back({B,L});
    408     rev[B].push_back({A,L});
    409   }
    410   for(int i=0;i<N;i++){
    411     if(vis[i]!=1){
    412       dfs_fwd(i);
    413     }
    414   }
    415   std::reverse(ord.begin(),ord.end());
    416   for(int i:ord){
    417     if(vis[i]!=2){
    418       cc[i]=ncc++;
    419       offset[i]=0;
    420       dfs_rev(i);
    421     }
    422   }
    423   int Q;
    424   scanf("%d",&Q);
    425   for(int i=0;i<Q;i++){
    426     int V,S,T;
    427     scanf("%d %d %d",&V,&S,&T);
    428     V--;
    429     assert(0<=S&&S<T);
    430     if(S%gcd(loop[cc[V]],T)==0){
    431       printf("YES\n");
    432     }else{
    433       printf("NO\n");
    434     }
    435   }
    436 }
    437 ```
    438 
    439 [1515H - Phoenix and Bits](/contest/1515/problem/H "Codeforces Global Round 14")
    440 
    441 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
    442 
    443 **Tutorial**
    444 
    445 Tutorial is loading...
    446 
    447 **Solution**
    448 
    449 ```
    450 #include <cstdio>
    451 #include <cassert>
    452 #include <utility>
    453 #include <functional>
    454 
    455 //numbers up to 2^MAXLOGX-1
    456 const int MAXLOGX=20;
    457 
    458 template<int k>
    459 struct Trie{
    460   Trie<k-1>* chd[2];
    461   int cnt;
    462   int lazy;
    463   int has[2];
    464   int get_cnt(){
    465     assert(this!=NULL);
    466     return cnt;
    467   }
    468   int get_has(int d){
    469     assert(this!=NULL);
    470     push();
    471     assert(has[d]<(1<<(k+1)));
    472     return has[d];
    473   }
    474   Trie(Trie<k-1>* l,Trie<k-1>* r):chd{l,r},cnt(0),lazy(0),has{0,0}{
    475     if(l){
    476       cnt+=l->get_cnt();
    477       has[0]|=l->get_has(0)|(1<<k);
    478       has[1]|=l->get_has(1);
    479     }
    480     if(r){
    481       cnt+=r->get_cnt();
    482       has[0]|=r->get_has(0);
    483       has[1]|=r->get_has(1)|(1<<k);
    484     }
    485     assert(has[0]<(1<<(k+1)));
    486     assert(has[1]<(1<<(k+1)));
    487   }
    488   void push(){
    489     assert(lazy<(1<<(k+1)));
    490     if(!lazy) return;
    491     //handle kth bit
    492     if(lazy&(1<<k)){
    493       std::swap(chd[0],chd[1]);
    494       if((has[0]^has[1])&(1<<k)){
    495 	has[0]^=(1<<k);
    496 	has[1]^=(1<<k);
    497       }
    498       lazy^=(1<<k);
    499     }
    500     //handle rest of bits
    501     int flip=(has[0]^has[1])&lazy;
    502     has[0]^=flip;
    503     has[1]^=flip;
    504     if(chd[0]) chd[0]->lazy^=lazy;
    505     if(chd[1]) chd[1]->lazy^=lazy;
    506     lazy=0;
    507     assert(has[0]<(1<<(k+1)));
    508     assert(has[1]<(1<<(k+1)));
    509   }
    510 };
    511 
    512 template<>
    513 struct Trie<-1>{
    514   int lazy;
    515   Trie():lazy(0){
    516   }
    517   int get_cnt(){
    518     assert(this!=NULL);
    519     return 1;
    520   }
    521   int get_has(int d){
    522     assert(this!=NULL);
    523     return 0;
    524   }
    525 };
    526 
    527 template<int k>
    528 Trie<k>* create(int x){
    529   if(x&(1<<k)){
    530     return new Trie<k>(NULL,create<k-1>(x));
    531   }else{
    532     return new Trie<k>(create<k-1>(x),NULL);
    533   }
    534 }
    535 template<>
    536 Trie<-1>* create(int x){
    537   return new Trie<-1>();
    538 }
    539 
    540 template<int k>
    541 std::pair<Trie<k-1>*,Trie<k-1>*> destruct(Trie<k>* a){
    542   assert(a!=NULL);
    543   a->push();
    544   auto res=std::make_pair(a->chd[0],a->chd[1]);
    545   delete a;
    546   return res;
    547 }
    548 
    549 template<int k>
    550 Trie<k>* join(Trie<k-1>* l,Trie<k-1>* r){
    551   if(l==NULL&&r==NULL) return NULL;
    552   return new Trie<k>(l,r);
    553 }
    554 
    555 template<int k>
    556 Trie<k>* merge(Trie<k>* a,Trie<k>* b){
    557   if(!a) return b;
    558   if(!b) return a;
    559   auto aa=destruct(a);
    560   auto bb=destruct(b);
    561   Trie<k-1>* l=merge<k-1>(aa.first,bb.first);
    562   Trie<k-1>* r=merge<k-1>(aa.second,bb.second);
    563   return join<k>(l,r);
    564 }
    565 
    566 template<>
    567 Trie<-1>* merge<-1>(Trie<-1>* a,Trie<-1>* b){
    568   if(!a) return b;
    569   if(!b) return a;
    570   delete b;
    571   return a;
    572 }
    573 
    574 template<int k>
    575 //<thres and >=thres
    576 std::pair<Trie<k>*,Trie<k>*> split(Trie<k>* a,int thres){
    577   if(a==NULL){
    578     return {NULL,NULL};
    579   }
    580   if(thres<=0) return {NULL,a};
    581   if(thres>=(1<<(k+1))) return {a,NULL};
    582   assert(k>=0);
    583   auto aa=destruct(a);
    584   if(thres<(1<<k)){
    585     Trie<k-1>* l,*r;
    586     std::tie(l,r)=split<k-1>(aa.first,thres);
    587     return std::make_pair(join<k>(l,NULL),join<k>(r,aa.second));
    588   }else if(thres>(1<<k)){
    589     Trie<k-1>* l,*r;
    590     std::tie(l,r)=split<k-1>(aa.second,thres-(1<<k));
    591     return std::make_pair(join<k>(aa.first,l),join<k>(NULL,r));
    592   }else{
    593     return std::make_pair(join<k>(aa.first,NULL),join<k>(NULL,aa.second));
    594   }
    595 }
    596 
    597 template<>
    598 std::pair<Trie<-1>*,Trie<-1>*> split<-1>(Trie<-1>* a,int thres){
    599   assert(0);
    600 }
    601 
    602 template<int k>
    603 Trie<k>* update(Trie<k>* a,int val){
    604   if(a==NULL) return NULL;
    605   a->push();
    606   assert(val<(1<<(k+1)));
    607   if((val&a->has[0]&a->has[1])==0){
    608     a->lazy^=(val&a->has[0]);
    609     return a;
    610   }
    611   Trie<k-1>* l,*r;
    612   std::tie(l,r)=destruct(a);
    613   l=update<k-1>(l,val&~(1<<k));
    614   r=update<k-1>(r,val&~(1<<k));
    615   if(val&(1<<k)){
    616     return join<k>(NULL,merge<k-1>(l,r));
    617   }else{
    618     return join<k>(l,r);
    619   }
    620 }
    621 
    622 template<>
    623 Trie<-1>* update<-1>(Trie<-1>* a,int val){
    624   return a;
    625 }
    626 
    627 int main(){
    628   Trie<MAXLOGX-1>* root=NULL;
    629   int N,Q;
    630   scanf("%d %d",&N,&Q);
    631   for(int i=0;i<N;i++){
    632     int A;
    633     scanf("%d",&A);
    634     root=merge(root,create<MAXLOGX-1>(A));
    635   }
    636   for(int i=0;i<Q;i++){
    637     int T,L,R;
    638     scanf("%d %d %d",&T,&L,&R);
    639     Trie<MAXLOGX-1>* left,*right;
    640     std::tie(left,root)=split(root,L);
    641     std::tie(root,right)=split(root,R+1);
    642     if(T==4){
    643       printf("%d\n",root?root->cnt:0);
    644     }else{
    645       int X;
    646       scanf("%d",&X);
    647       if(root!=NULL){
    648 	if(T==1){
    649 	  root->lazy^=((1<<MAXLOGX)-1);
    650 	  root=update(root,X^((1<<MAXLOGX)-1));
    651 	  root->lazy^=((1<<MAXLOGX)-1);
    652 	}else if(T==2){
    653 	  root=update(root,X);
    654 	}else if(T==3){
    655 	  assert(X<(1<<MAXLOGX));
    656 	  root->lazy^=X;
    657 	}
    658       }
    659     }
    660     root=merge(root,left);
    661     root=merge(root,right);
    662   }
    663 }
    664 ```
    665 
    666 [1515I - Phoenix and Diamonds](/contest/1515/problem/I "Codeforces Global Round 14")
    667 
    668 Idea: [dragonslayerintraining](/profile/dragonslayerintraining "Grandmaster dragonslayerintraining")
    669 
    670 **Tutorial**
    671 
    672 Tutorial is loading...
    673 
    674 **Solution**
    675 
    676 ```
    677 #include <cstdio>
    678 #include <algorithm>
    679 #include <functional>
    680 #include <utility>
    681 #include <numeric>
    682 #include <cassert>
    683 
    684 using ll=long long;
    685 
    686 const ll INF=1e18+7;
    687 
    688 struct Diamond{
    689   int w,v,t;
    690   ll a;
    691 }diamonds[200005];
    692 int index[200005];
    693 int N;
    694 
    695 struct Node{
    696   ll sum_w[31];//sum of weights of all diamonds with weight <2^k
    697   ll sum_v[31];//sum of values of all diamonds with weight <2^k
    698   ll one_w[31];//sum of weights of light+first heavy when restricted to <2^k
    699   ll one_v[31];//sum of values of light+first heavy when restricted to <2^k
    700 }st[800005];
    701 
    702 void rebuild(int w,int L,int R,int a,int b){
    703   if(a>=R||b<=L) return;
    704   if(R-L==1){
    705     for(int k=1;k<=30;k++){
    706       st[w].sum_w[k]=diamonds[L].a*diamonds[L].w*(diamonds[L].w<(1<<k));
    707       st[w].sum_v[k]=diamonds[L].a*diamonds[L].v*(diamonds[L].w<(1<<k));
    708       st[w].one_w[k]=INF;//query capacity never exceed INF
    709       st[w].one_v[k]=INF;
    710       if(diamonds[L].w>=(1<<(k-1))&&diamonds[L].w<(1<<k)&&diamonds[L].a>0){
    711 	st[w].one_w[k]=diamonds[L].w;
    712 	st[w].one_v[k]=diamonds[L].v;
    713       }
    714     }
    715   }else{
    716     int M=(L+R)/2;
    717     rebuild(w*2+1,L,M,a,b);
    718     rebuild(w*2+2,M,R,a,b);
    719     for(int k=1;k<=30;k++){
    720       st[w].sum_w[k]=st[w*2+1].sum_w[k]+st[w*2+2].sum_w[k];
    721       st[w].sum_v[k]=st[w*2+1].sum_v[k]+st[w*2+2].sum_v[k];
    722       if(st[w*2+1].one_w[k]<st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k]){
    723 	st[w].one_w[k]=st[w*2+1].one_w[k];
    724 	st[w].one_v[k]=st[w*2+1].one_v[k];
    725       }else{
    726 	st[w].one_w[k]=st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k];
    727 	st[w].one_v[k]=st[w*2+1].sum_v[k-1]+st[w*2+2].one_v[k];
    728       }
    729     }
    730   }
    731 }
    732 
    733 //only consider weights <2^k
    734 //take maximal prefix possible
    735 void query_all(int w,int L,int R,int& i,int k,ll& cap,ll& value){
    736   assert(i>=L&&i<=R);
    737   assert(R-L>0);
    738   if(i==R) return;
    739   if(i==L&&st[w].sum_w[k]<=cap){
    740     cap-=st[w].sum_w[k];
    741     value+=st[w].sum_v[k];
    742     i=R;
    743   }else if(R-L>1){
    744     int M=(L+R)/2;
    745     if(i<M){
    746       query_all(w*2+1,L,M,i,k,cap,value);
    747     }
    748     if(i>=M){
    749       query_all(w*2+2,M,R,i,k,cap,value);
    750     }
    751   }
    752 }
    753 
    754 std::array<ll,2> query_one_range_simpl(int w,int L,int R,int a,int b,int k){
    755   if(a>=R||b<=L) return {INF,0};
    756   if(a<=L&&b>=R){
    757     return {st[w].one_w[k],st[w].sum_w[k-1]};
    758   }else{
    759     int M=(L+R)/2;
    760     std::array<ll,2> lsum,rsum;
    761     lsum=query_one_range_simpl(w*2+1,L,M,a,b,k);
    762     rsum=query_one_range_simpl(w*2+2,M,R,a,b,k);
    763     if(lsum[0]<lsum[1]+rsum[0]){
    764       return {lsum[0],lsum[1]+rsum[1]};
    765     }else{
    766       return {lsum[1]+rsum[0],lsum[1]+rsum[1]};
    767     }
    768   }
    769 }
    770 
    771 std::array<ll,4> query_one_range(int w,int L,int R,int a,int b,int k){
    772   if(a>=R||b<=L) return {INF,INF,0,0};
    773   if(a<=L&&b>=R){
    774     return {st[w].one_w[k],st[w].one_v[k],st[w].sum_w[k-1],st[w].sum_v[k-1]};
    775   }else{
    776     int M=(L+R)/2;
    777     std::array<ll,4> lsum,rsum;
    778     lsum=query_one_range(w*2+1,L,M,a,b,k);
    779     rsum=query_one_range(w*2+2,M,R,a,b,k);
    780     if(lsum[0]<lsum[2]+rsum[0]){
    781       return {lsum[0],lsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
    782     }else{
    783       return {lsum[2]+rsum[0],lsum[3]+rsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
    784     }
    785   }
    786 }
    787 
    788 //returns min j such that one_w[i..j) <= cap, or -1 if none exist
    789 //reduce cap by weight of light in [max(i,L),R)
    790 int query_one_range_search_(int w,int L,int R,int& i,int k,ll& cap){
    791   assert(i>=L&&i<=R);
    792   assert(R-L>0);
    793   if(i==R) return -1;
    794   if(i==L&&st[w].one_w[k]>cap){
    795     cap-=st[w].sum_w[k-1];
    796     i=R;
    797     return -1;
    798   }else if(R-L==1){
    799     assert(i==L);
    800     assert(st[w].one_w[k]<=cap);
    801     cap-=st[w].sum_w[k-1];
    802     i=R;
    803     return R;
    804   }else{
    805     int M=(L+R)/2;
    806     int res=-1;
    807     if(i<M){
    808       res=query_one_range_search_(w*2+1,L,M,i,k,cap);
    809     }
    810     if(res!=-1) return res;
    811     if(i>=M){
    812       res=query_one_range_search_(w*2+2,M,R,i,k,cap);
    813     }
    814     return res;
    815   }
    816 }
    817 
    818 int query_one_range_search(int i,int k,ll cap){
    819   //note this copy of cap will be modified
    820   return query_one_range_search_(0,0,N,i,k,cap);
    821 }
    822 
    823 void query_one(int& L,int k,ll& cap,ll& value){
    824   int high=query_one_range_search(L,k,cap);
    825   //v[high]<=cap
    826   if(high!=-1){
    827     auto v=query_one_range(0,0,N,L,high,k);
    828     L=high;
    829     cap-=v[0];
    830     value+=v[1];
    831   }
    832 }
    833 
    834 ll query(ll cap){
    835   ll value=0;
    836   int i=0;
    837   for(int k=30;k>0;k--){
    838     query_all(0,0,N,i,k,cap,value);
    839     if(i==N) break;
    840     ll take=std::min(diamonds[i].a,cap/diamonds[i].w);
    841     cap-=take*diamonds[i].w;
    842     value+=take*diamonds[i].v;
    843     i++;
    844     query_one(i,k,cap,value);
    845   }
    846   return value;
    847 }
    848 
    849 int main(){
    850   int Q;
    851   scanf("%d %d",&N,&Q);
    852   for(int i=0;i<N;i++){
    853     scanf("%lld %d %d",&diamonds[i].a,&diamonds[i].w,&diamonds[i].v);
    854     diamonds[i].t=i;
    855   }
    856   std::sort(diamonds,diamonds+N,[](Diamond x,Diamond y){
    857       return (x.v!=y.v)?(x.v>y.v):(x.w<y.w);
    858     });
    859   for(int i=0;i<N;i++){
    860     index[diamonds[i].t]=i;
    861   }
    862   rebuild(0,0,N,0,N);
    863   for(int i=0;i<Q;i++){
    864     int T;
    865     scanf("%d",&T);
    866     if(T==1){
    867       int K,D;
    868       scanf("%d %d",&K,&D);
    869       D--;
    870       diamonds[index[D]].a+=K;
    871       rebuild(0,0,N,index[D],index[D]+1);
    872     }else if(T==2){
    873       int K,D;
    874       scanf("%d %d",&K,&D);
    875       D--;
    876       diamonds[index[D]].a-=K;
    877       assert(diamonds[index[D]].a>=0);
    878       rebuild(0,0,N,index[D],index[D]+1);
    879     }else{
    880       ll C;
    881       scanf("%lld",&C);
    882       printf("%lld\n",query(C));
    883     }
    884   }
    885 }
    886 ```