codeforces-scrape

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

2240.md (31938B)


      1 Source: https://codeforces.com/blog/entry/154788
      2 
      3 Thanks everybody for participating in the round!
      4 
      5 ### [Div2A. Another Popcount Problem](https://codeforces.com/contest/2240/problem/A)
      6 
      7 Author: [wangmarui](/profile/wangmarui "Grandmaster wangmarui") Preparation: [wangmarui](/profile/wangmarui "Grandmaster wangmarui")
      8 
      9 **Hint 1**
     10 
     11 Consider each binary bit independently.
     12 
     13 **Hint 2**
     14 
     15 Think about a greedy approach.
     16 
     17 **Solution**
     18 
     19 Tutorial is loading...
     20 
     21 **Code (by wangmarui)**
     22 
     23 ```
     24 /*
     25 author: Yuneko
     26 
     27 time: 2026/5/5
     28 
     29 contest:
     30 
     31 Tips:
     32 
     33 RE, MLE?
     34 greedy, dp?
     35 natural time?
     36 map, umap?
     37 giveup rating, get score.
     38 brute force, right solution?
     39 %mod? std/run/maker/checker?
     40 add bruteforce?
     41 clear?
     42 double, long double?
     43 O(n)? O(n^2)!
     44 make data!
     45 
     46 last but not least.
     47 
     48 bruteforce -> SegTree?
     49 Think more.
     50 */
     51 //#pragma GCC optimize("Ofast")
     52 //#pragma GCC optimize("unroll-loops")
     53 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
     54 #include<bits/stdc++.h>
     55 using namespace std;
     56 //#define map unordered_map
     57 #define re register
     58 #define ll long long
     59 #define cll const ll
     60 #define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
     61 #define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
     62 #define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))
     63 #define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))
     64 #define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)
     65 #define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)
     66 #define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))
     67 #define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))
     68 #define pii pair<ll,ll>
     69 #define mid ((l+r)>>1)
     70 #define lowbit(x) ((x)&-(x))
     71 #define pb push_back
     72 #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
     73 #define endl '\n'
     74 #define QwQ return 0;
     75 #define db long double
     76 #define ull unsigned long long
     77 #define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))
     78 #define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)
     79 #define x first
     80 #define y second
     81 #define aty cout<<"Yes\n";
     82 #define atn cout<<"No\n";
     83 #define cfy cout<<"YES\n";
     84 #define cfn cout<<"NO\n";
     85 #define xxy cout<<"yes\n";
     86 #define xxn cout<<"no\n";
     87 #define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
     88 #define printat(x) x?cout<<"Yes\n":cout<<"No\n";
     89 #define printxx(x) x?cout<<"yes\n":cout<<"no\n";
     90 #define maxqueue priority_queue<ll>
     91 #define minqueue priority_queue<ll,vector<ll>,greater<ll>>
     92 #define bug1 cout<<"bug1,AWaDa?\n";
     93 #define bug2 cout<<"bug2,AWaDa!\n";
     94 #define bug3 cout<<"bug3,AKTang?\n";
     95 #define bug4 cout<<"bug4,AKTang!\n";
     96 #define IM (ll)1e9
     97 #define LM (ll)1e18
     98 #define MIM (ll)-1e9
     99 #define MLM (ll)-1e18
    100 #define sort stable_sort
    101 ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}
    102 ll pw(ll x,ll y,ll mod){if(mod==1)return 0;if(y==0)return 1;if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
    103 ll pw(ll x){return 1ll<<x;}
    104 template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}ll Ss=chrono::steady_clock::now().time_since_epoch().count();mt19937_64 Apple(Ss);ll rand_lr(ll l,ll r){return Apple()%(r-l+1)+l;}
    105 cll mod=1e9+7,N=300010;ll fac[N],inv[N];void init(){fac[0]=1;forl(i,1,N-5)fac[i]=i*fac[i-1],fac[i]%=mod;inv[N-5]=pw(fac[N-5],mod-2,mod);forr(i,N-5,1)inv[i-1]=inv[i]*i%mod;}ll C(ll n,ll m){if(n<m || m<0)return 0;return (fac[n]%mod)*(inv[n-m]*inv[m]%mod)%mod;}
    106 void add(ll&x,ll y){x=((x+y)%mod+mod)%mod;}void del(ll&x,ll y){x=(x%mod-y%mod+mod)%mod;}
    107 ll _t_;
    108 struct BIT{
    109     ll maxn;
    110     ll tree[1000010];
    111     void clear(ll l){
    112         forl(i,0,l)
    113             tree[i]=0;
    114     }
    115     void add(ll x,ll y){
    116         for(;x<=maxn;x+=lowbit(x))
    117             tree[x]+=y;
    118     }
    119     ll query(ll x){
    120         ll S=0;
    121         for(;x;x-=lowbit(x))
    122             S+=tree[x];
    123         return S;
    124     }
    125     ll query(ll l,ll r){
    126         return query(r)-query(l-1);
    127     }
    128 };
    129 ll lg[1000010];
    130 void Init(){
    131     forl(i,2,1e6+5)
    132         lg[i]=lg[i>>1]+1;
    133 }
    134 //xw
    135 ll n,m;
    136 ll ans;
    137 //st
    138 void _clear(){}
    139 void solve()
    140 {
    141     _clear();
    142 	cin>>n>>m;
    143 	forl(i,0,30)
    144 	{
    145 		ll num=min(n/pw(i),m);
    146 		ans+=num,n-=num*pw(i);
    147 	}
    148 	cout<<ans<<endl;
    149 	ans=0;
    150 }
    151 int main()
    152 {
    153     Init();
    154 //    freopen("tst.txt","r",stdin);
    155 //    freopen("sans.txt","w",stdout);
    156     IOS;
    157     _t_=1;
    158     cin>>_t_;
    159     while(_t_--)
    160         solve();
    161     QwQ;
    162 }
    163 ```
    164 
    165 ### [Div2B. AI Finds Nothing Here](https://codeforces.com/contest/2240/problem/B)
    166 
    167 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526")
    168 
    169 **Hint 1**
    170 
    171 Try some special cases, such as $r=c=2$, $n=r$, or $m=c$, etc.
    172 
    173 **Solution**
    174 
    175 In terms of systems of equations, the given problem fixes for us the parities of at most (and exactly) $(n-r+1)\cdot(m-c+1)$ cells (by giving us a system of equations to solve with that many equations). What this means is that, if we are to fill an upper border of thickness $r-1$ and a left border of thickness of $c-1$, then every cell from that point onward is determined uniquely by some equation (Tip: imagine how this pans out for a $2\times2$ matrix; after filling the first row and left column arbitrarily, cell (2,2) is uniquely determined, then (2,3), and so on).
    176 
    177 Therefore, the answer is $2^{nm - (n-r+1)(m-c+1)}$.
    178 
    179 **Code (by Gold14526)**
    180 
    181 ```
    182 #include<bits/stdc++.h>
    183 #define cint const int
    184 #define uint unsigned int
    185 #define cuint const unsigned int
    186 #define ll long long
    187 #define cll const long long
    188 #define ull unsigned long long
    189 #define cull const unsigned long long
    190 using namespace std;
    191 namespace FastIO
    192 {
    193     const int BUF_SIZE=1<<20;
    194     char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    195     char* in_ptr=in_buf+BUF_SIZE;
    196     char* out_ptr=out_buf;
    197     char get_char()
    198     {
    199         if(in_ptr==in_buf+BUF_SIZE)
    200         {
    201             in_ptr=in_buf;
    202             fread(in_buf,1,BUF_SIZE,stdin);
    203         }
    204         return *in_ptr++;
    205     }
    206     void put_char(char c)
    207     {
    208         if(out_ptr==out_buf+BUF_SIZE)
    209         {
    210             fwrite(out_buf,1,BUF_SIZE,stdout);
    211             out_ptr=out_buf;
    212         }
    213         *out_ptr++=c;
    214     }
    215     struct Flusher
    216     {
    217         ~Flusher()
    218         {
    219             if(out_ptr!=out_buf)
    220             {
    221                 fwrite(out_buf,1,out_ptr-out_buf,stdout);
    222             }
    223         }
    224     } flusher;
    225 }
    226 #define getchar FastIO::get_char
    227 #define putchar FastIO::put_char
    228 inline int read()
    229 {
    230     int x=0;
    231     bool zf=1;
    232     char ch=getchar();
    233     while(ch<'0'||ch>'9')
    234     {
    235         if(ch=='-')
    236         {
    237             zf=0;
    238         }
    239         ch=getchar();
    240     }
    241     while(ch>='0'&&ch<='9')
    242     {
    243         x=(x<<1)+(x<<3)+(ch^48);
    244         ch=getchar();
    245     }
    246     return zf?x:-x;
    247 }
    248 void print(cint x)
    249 {
    250     if(x==0)
    251     {
    252         putchar('0');
    253         return;
    254     }
    255     char buf[12];
    256     int len=0,y=x;
    257     if(y<0)
    258     {
    259         putchar('-');
    260         y=-y;
    261     }
    262     while(y)
    263     {
    264         buf[len++]=(y%10)+'0';
    265         y/=10;
    266     }
    267     while(len--)
    268     {
    269         putchar(buf[len]);
    270     }
    271 }
    272 inline void princh(cint x,const char ch)
    273 {
    274     print(x);
    275     putchar(ch);
    276 }
    277 cint mod=998244353;
    278 int n,m,r,c;
    279 int qpow(int x,int y)
    280 {
    281     int res=1;
    282     while(y)
    283     {
    284         if(y&1)res=1ll*res*x%mod;
    285         x=1ll*x*x%mod;
    286         y>>=1;
    287     }
    288     return res;
    289 }
    290 void solve()
    291 {
    292     n=read();
    293     m=read();
    294     r=read();
    295     c=read();
    296     princh(qpow(2,(1ll*n*(c-1)+1ll*m*(r-1)-1ll*(c-1)*(r-1))%(mod-1)),'\n');
    297 }
    298 int main()
    299 {
    300     // freopen(".in","r",stdin);
    301     // freopen(".out","w",stdout);
    302     int T=read();
    303     while(T--)solve();
    304     return 0;
    305 }
    306 ```
    307 
    308 ### [Div1A. Nim Game Is XOR Game](https://codeforces.com/contest/2239/problem/A)
    309 
    310 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526")
    311 
    312 **Hint 1**
    313 
    314 Try working through some cases by hand. You may notice that whenever there is more than one non-zero number, the first player wins. Then think about why this is true.
    315 
    316 **Solution**
    317 
    318 Tutorial is loading...
    319 
    320 **Code (by Gold14526)**
    321 
    322 ```
    323 #include<bits/stdc++.h>
    324 #define cint const int
    325 #define uint unsigned int
    326 #define cuint const unsigned int
    327 #define ll long long
    328 #define cll const long long
    329 #define ull unsigned long long
    330 #define cull const unsigned long long
    331 using namespace std;
    332 namespace FastIO
    333 {
    334     const int BUF_SIZE=1<<20;
    335     char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    336     char* in_ptr=in_buf+BUF_SIZE;
    337     char* out_ptr=out_buf;
    338     char get_char()
    339     {
    340         if(in_ptr==in_buf+BUF_SIZE)
    341         {
    342             in_ptr=in_buf;
    343             fread(in_buf,1,BUF_SIZE,stdin);
    344         }
    345         return *in_ptr++;
    346     }
    347     void put_char(char c)
    348     {
    349         if(out_ptr==out_buf+BUF_SIZE)
    350         {
    351             fwrite(out_buf,1,BUF_SIZE,stdout);
    352             out_ptr=out_buf;
    353         }
    354         *out_ptr++=c;
    355     }
    356     struct Flusher
    357     {
    358         ~Flusher()
    359         {
    360             if(out_ptr!=out_buf)
    361             {
    362                 fwrite(out_buf,1,out_ptr-out_buf,stdout);
    363             }
    364         }
    365     } flusher;
    366 }
    367 #define getchar FastIO::get_char
    368 #define putchar FastIO::put_char
    369 inline int read()
    370 {
    371     int x=0;
    372     bool zf=1;
    373     char ch=getchar();
    374     while(ch<'0'||ch>'9')
    375     {
    376         if(ch=='-')
    377         {
    378             zf=0;
    379         }
    380         ch=getchar();
    381     }
    382     while(ch>='0'&&ch<='9')
    383     {
    384         x=(x<<1)+(x<<3)+(ch^48);
    385         ch=getchar();
    386     }
    387     return zf?x:-x;
    388 }
    389 void print(cint x)
    390 {
    391     if(x==0)
    392     {
    393         putchar('0');
    394         return;
    395     }
    396     char buf[12];
    397     int len=0,y=x;
    398     if(y<0)
    399     {
    400         putchar('-');
    401         y=-y;
    402     }
    403     while(y)
    404     {
    405         buf[len++]=(y%10)+'0';
    406         y/=10;
    407     }
    408     while(len--)
    409     {
    410         putchar(buf[len]);
    411     }
    412 }
    413 inline void princh(cint x,const char ch)
    414 {
    415     print(x);
    416     putchar(ch);
    417 }
    418 cint N=1e6;
    419 int n,a[N+1],s,ans;
    420 void solve()
    421 {
    422     n=read();
    423     s=0;
    424     ans=0;
    425     for(int i=1;i<=n;++i)s^=(a[i]=read());
    426     if(n==1)
    427     {
    428         princh(0,'\n');
    429         return;
    430     }
    431     if(!s)
    432     {
    433         princh(1,'\n');
    434         return;
    435     }
    436     for(int i=1;i<=n;++i)
    437     {
    438         if((s^a[i])<a[i])++ans;
    439     }
    440     princh(ans,'\n');
    441 }
    442 int main()
    443 {
    444     // freopen(".in","r",stdin);
    445     // freopen(".out","w",stdout);
    446     int T=read();
    447     while(T--)solve();
    448     return 0;
    449 }
    450 ```
    451 
    452 ### [Div1B. Decidophobia](https://codeforces.com/contest/2239/problem/B)
    453 
    454 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526")
    455 
    456 **Hint 1**
    457 
    458 How does everyone’s contribution change when you give a gift to someone?
    459 
    460 **Solution**
    461 
    462 Tutorial is loading...
    463 
    464 **Code (by Gold14526)**
    465 
    466 ```
    467 #include<bits/stdc++.h>
    468 #define cint const int
    469 #define uint unsigned int
    470 #define cuint const unsigned int
    471 #define ll long long
    472 #define cll const long long
    473 #define ull unsigned long long
    474 #define cull const unsigned long long
    475 #define sh short
    476 #define csh const short
    477 #define ush unsigned short
    478 #define cush const unsigned short
    479 using namespace std;
    480 namespace FastIO
    481 {
    482     const int BUF_SIZE=1<<20;
    483     char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    484     char* in_ptr=in_buf+BUF_SIZE;
    485     char* out_ptr=out_buf;
    486     char get_char()
    487     {
    488         if(in_ptr==in_buf+BUF_SIZE)
    489         {
    490             in_ptr=in_buf;
    491             fread(in_buf,1,BUF_SIZE,stdin);
    492         }
    493         return *in_ptr++;
    494     }
    495     void put_char(char c)
    496     {
    497         if(out_ptr==out_buf+BUF_SIZE)
    498         {
    499             fwrite(out_buf,1,BUF_SIZE,stdout);
    500             out_ptr=out_buf;
    501         }
    502         *out_ptr++=c;
    503     }
    504     struct Flusher
    505     {
    506         ~Flusher()
    507         {
    508             if(out_ptr!=out_buf)
    509             {
    510                 fwrite(out_buf,1,out_ptr-out_buf,stdout);
    511             }
    512         }
    513     } flusher;
    514 }
    515 #define getchar FastIO::get_char
    516 #define putchar FastIO::put_char
    517 inline int read()
    518 {
    519     int x=0;
    520     bool zf=1;
    521     char ch=getchar();
    522     while(ch<'0'||ch>'9')
    523     {
    524         if(ch=='-')
    525         {
    526             zf=0;
    527         }
    528         ch=getchar();
    529     }
    530     while(ch>='0'&&ch<='9')
    531     {
    532         x=(x<<1)+(x<<3)+(ch^48);
    533         ch=getchar();
    534     }
    535     return zf?x:-x;
    536 }
    537 void print(cll x)
    538 {
    539     if(x==0)
    540     {
    541         putchar('0');
    542         return;
    543     }
    544     char buf[20];
    545     int len=0;
    546     ll y=x;
    547     if(y<0)
    548     {
    549         putchar('-');
    550         y=-y;
    551     }
    552     while(y)
    553     {
    554         buf[len++]=(y%10)+'0';
    555         y/=10;
    556     }
    557     while(len--)
    558     {
    559         putchar(buf[len]);
    560     }
    561 }
    562 inline void princh(cll x,const char ch)
    563 {
    564     print(x);
    565     putchar(ch);
    566 }
    567 cint N=6e5;
    568 int n,d;
    569 int a[N+1];
    570 ll s[N+1],val[N+1];
    571 ll ans;
    572 void solve()
    573 {
    574     n=read();
    575     d=read();
    576     for(int i=1;i<=n;++i)
    577     {
    578         a[i]=a[i+n]=a[i+(n<<1)]=read();
    579     }
    580     for(int i=1;i<=n*3;++i)s[i]=s[i-1]+a[i];
    581     for(int i=n+1;i<=(n<<1);++i)
    582     {
    583         val[i-n]=1ll*(d<<1|1)*a[i]-(s[i+d]-s[i-d-1]);
    584     }
    585     ans=0;
    586     for(int i=1;i<=n;++i)ans+=max(0ll,val[i]);
    587     princh(ans,'\n');
    588 }
    589 int main()
    590 {
    591     //freopen(".in","r",stdin);
    592     //freopen(".out","w",stdout);
    593     int T=read();
    594     while(T--)solve();
    595     return 0;
    596 }
    597 ```
    598 
    599 ### [Div1C. Revival](https://codeforces.com/contest/2239/problem/C)
    600 
    601 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526")
    602 
    603 **Hint 1**
    604 
    605 Consider determining all the numbers from back to front.
    606 
    607 **Hint 2**
    608 
    609 When you determine a number, subtract $1$ from all previous values that are greater than this number. This way, all $p$ values decrease by one, while all $s$ values remain unchanged. Now you only need to solve the problem of determining the last number.
    610 
    611 **Solution**
    612 
    613 Tutorial is loading...
    614 
    615 **Code (by Gold14526)**
    616 
    617 ```
    618 #include<bits/stdc++.h>
    619 #define cint const int
    620 #define uint unsigned int
    621 #define cuint const unsigned int
    622 #define ll long long
    623 #define cll const long long
    624 #define ull unsigned long long
    625 #define cull const unsigned long long
    626 #define sh short
    627 #define csh const short
    628 #define ush unsigned short
    629 #define cush const unsigned short
    630 using namespace std;
    631 namespace FastIO
    632 {
    633     const int BUF_SIZE=1<<20;
    634     char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    635     char* in_ptr=in_buf+BUF_SIZE;
    636     char* out_ptr=out_buf;
    637     char get_char()
    638     {
    639         if(in_ptr==in_buf+BUF_SIZE)
    640         {
    641             in_ptr=in_buf;
    642             fread(in_buf,1,BUF_SIZE,stdin);
    643         }
    644         return *in_ptr++;
    645     }
    646     void put_char(char c)
    647     {
    648         if(out_ptr==out_buf+BUF_SIZE)
    649         {
    650             fwrite(out_buf,1,BUF_SIZE,stdout);
    651             out_ptr=out_buf;
    652         }
    653         *out_ptr++=c;
    654     }
    655     struct Flusher
    656     {
    657         ~Flusher()
    658         {
    659             if(out_ptr!=out_buf)
    660             {
    661                 fwrite(out_buf,1,out_ptr-out_buf,stdout);
    662             }
    663         }
    664     } flusher;
    665 }
    666 #define getchar FastIO::get_char
    667 #define putchar FastIO::put_char
    668 inline ll read()
    669 {
    670     ll x=0;
    671     bool zf=1;
    672     char ch=getchar();
    673     while(ch<'0'||ch>'9')
    674     {
    675         if(ch=='-')
    676         {
    677             zf=0;
    678         }
    679         ch=getchar();
    680     }
    681     while(ch>='0'&&ch<='9')
    682     {
    683         x=(x<<1)+(x<<3)+(ch^48);
    684         ch=getchar();
    685     }
    686     return zf?x:-x;
    687 }
    688 void print(cint x)
    689 {
    690     if(x==0)
    691     {
    692         putchar('0');
    693         return;
    694     }
    695     char buf[12];
    696     int len=0,y=x;
    697     if(y<0)
    698     {
    699         putchar('-');
    700         y=-y;
    701     }
    702     while(y)
    703     {
    704         buf[len++]=(y%10)+'0';
    705         y/=10;
    706     }
    707     while(len--)
    708     {
    709         putchar(buf[len]);
    710     }
    711 }
    712 inline void princh(cint x,const char ch)
    713 {
    714     print(x);
    715     putchar(ch);
    716 }
    717 cint N=1e6;
    718 int n;
    719 ll val[N+1];
    720 char type[N+1];
    721 int ans[N+1];
    722 struct Binary_Index_Tree{
    723     int a[N+1];
    724     void clear()
    725     {
    726         for(int i=1;i<=n;++i)a[i]=0;
    727     }
    728     inline void add(cint x,cint y)
    729     {
    730         for(int i=x;i<=n;i+=(i&-i))a[i]+=y;
    731     }
    732     inline int ask(cint x)
    733     {
    734         int s=0;
    735         for(int i=x;i;i-=(i&-i))s+=a[i];
    736         return s;
    737     }
    738     inline int find(int x)
    739     {
    740         int res=0;
    741         for(int len=1<<__lg(n);len;len>>=1)
    742         {
    743             if(res+len>n)continue;
    744             if(a[res+len]<=x)
    745             {
    746                 res+=len;
    747                 x-=a[res];
    748             }
    749         }
    750         return res+1;
    751     }
    752 }T;
    753 int lst[N+1];
    754 void solve()
    755 {
    756     n=read();
    757     T.clear();
    758     for(int i=1;i<=n;++i)
    759     {
    760         char ch=getchar();
    761         while(ch!='p'&&ch!='s')ch=getchar();
    762         type[i]=ch;
    763         val[i]=read();
    764         if(type[i]=='p')ans[i]=val[i];
    765         else val[i]=1ll*i*(i-1)/2-val[i];
    766     }
    767     for(int i=1;i<=n;++i)lst[i]=(type[i]=='s'?i:lst[i-1]);
    768     for(int i=1;i<=n;++i)T.add(i,1);
    769     for(int i=lst[n]+1;i<=n;++i)T.add(ans[i],-1);
    770     for(int i=lst[n];i;i=lst[i-1])
    771     {
    772         cint p=lst[i-1];
    773         ll d=val[i]-val[p];
    774         for(int j=i-1;j>p;--j)
    775         {
    776             d-=T.ask(ans[j]-1);
    777             T.add(ans[j],-1);
    778         }
    779         d+=i-p-1;
    780         for(int j=i-1;j>p;--j)T.add(ans[j],2);
    781         ans[i]=T.find(d);
    782         for(int j=i-1;j>p;--j)T.add(ans[j],-2);
    783         T.add(ans[i],-1);
    784     }
    785     for(int i=1;i<=n;++i)
    786     {
    787         princh(ans[i]," \n"[i==n]);
    788     }
    789 }
    790 int main()
    791 {
    792     //freopen(".in","r",stdin);
    793     //freopen(".out","w",stdout);
    794     int T=read();
    795     while(T--)solve();
    796     return 0;
    797 }
    798 ```
    799 
    800 ### [Div1D. Hunting the Beast](https://codeforces.com/contest/2239/problem/D)
    801 
    802 Author: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009") Preparation: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009")
    803 
    804 **Hint 1**
    805 
    806 By symmetry, all vertices are equivalent. Therefore, we only need to calculate the number of graphs in which a specific set is successful, and then multiply by $\binom{n}{m}$.
    807 
    808 **Hint 2**
    809 
    810 Let the nodes in the set be key nodes and the remaining nodes be non-key nodes. Consider the condition for the set to be successful and use the Principle of Inclusion-Exclusion to handle these conditions.
    811 
    812 **Hint 3**
    813 
    814 You might need to calculate the following: $n$ vertices form a set of disjoint cycles without self-loops. If there are $k$ cycles, the contribution is $(-1)^k$. Find the sum of contributions over all possible configurations.
    815 
    816 The answer is $1-n$, which you can try to prove.
    817 
    818 **Hint 4**
    819 
    820 Use the Binomial Theorem to simplify the sum.
    821 
    822 **Solution**
    823 
    824 Tutorial is loading...
    825 
    826 **Code (by Milkcat2009)**
    827 
    828 ```
    829 #include <bits/stdc++.h>
    830 #define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
    831 #define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
    832 #define CUP(i, l, r) for (int i = (l); i < (r); ++ i)
    833 #define fi first
    834 #define se second
    835 #define pb emplace_back
    836 #define mems(x, v) memset((x), (v), sizeof(x))
    837 #define memc(x, y) memcpy((x), (y), sizeof(x))
    838 #define SZ(x) (int)(x).size()
    839 #define ALL(x) (x).begin(), (x).end()
    840 #define ppc(x) __builtin_popcount(x)
    841 #define ctz(x) __builtin_ctz(x)
    842 #define clz(x) __builtin_clz(x)
    843 using namespace std;
    844 namespace math {
    845 	typedef long long LL;
    846 	template <class T> T qpow(T a, LL b) { if (!b) return {1}; T rs = a; b --; for (; b; b >>= 1, a = a * a) if (b & 1) rs = rs * a; return rs; }
    847 	LL mul(LL a, LL b, LL p) { LL rs = a * b - LL(1.L * a * b / p) * p; rs %= p; if (rs < 0) rs += p; return rs; }
    848 	template <unsigned P = 0> struct mint {
    849 		unsigned v; static unsigned mod; mint() = default;
    850 		template <class T> mint(T x) { x %= (int)getmod(), v = x < 0 ? x + getmod() : x; }
    851 		constexpr static unsigned getmod() { if (P > 0) return P; else return mod; }
    852 		static void setmod(unsigned m) { mod = m; }
    853 		mint operator + () const { return *this; }
    854 		mint operator - () const { return mint(0) - *this; }
    855 		mint inv() const { return assert(v), qpow(*this, getmod() - 2); }
    856 		int val() const { return v; }
    857 		mint &operator += (const mint &q) { if (v += q.v, v >= getmod()) v -= getmod(); return *this; }
    858 		mint &operator -= (const mint &q) { if (v -= q.v, v >= getmod()) v += getmod(); return *this; }
    859 		mint &operator *= (const mint &q) { v = 1ull * v * q.v % getmod(); return *this; }
    860 		mint &operator /= (const mint &q) { return *this *= q.inv(); }
    861 		friend mint operator + (mint p, const mint &q) { return p += q; }
    862 		friend mint operator - (mint p, const mint &q) { return p -= q; }
    863 		friend mint operator * (mint p, const mint &q) { return p *= q; }
    864 		friend mint operator / (mint p, const mint &q) { return p /= q; }
    865 		friend bool operator == (const mint &p, const mint &q) { return p.v == q.v; }
    866 		friend bool operator != (const mint &p, const mint &q) { return p.v != q.v; }
    867 		friend bool operator < (const mint &p, const mint &q) { return p.v < q.v; }
    868 		friend bool operator > (const mint &p, const mint &q) { return p.v > q.v; }
    869 		friend bool operator <= (const mint &p, const mint &q) { return p.v <= q.v; }
    870 		friend bool operator >= (const mint &p, const mint &q) { return p.v >= q.v; }
    871 		friend istream &operator >> (istream &is, mint &a) { LL x; is >> x, a = x; return is; }
    872 		friend ostream &operator << (ostream &os, const mint &a) { os << a.v; return os; }
    873 	};
    874 	template <> unsigned mint<0>::mod = 998244353;
    875 	template <typename MI>
    876 	struct Comb {
    877 		#define P MI::getmod()
    878 		vector<MI> fc, ifc;
    879 		void init(int n) {
    880 			fc.resize(n + 1), ifc.resize(n + 1), fc[0] = 1;
    881 			REP(i, 1, n) fc[i] = fc[i - 1] * i;
    882 			ifc[n] = fc[n].inv();
    883 			DEP(i, n, 1) ifc[i - 1] = ifc[i] * i;
    884 		}
    885 		MI operator () (LL n, LL m) {
    886 			if (m > n || m < 0 || n < 0) return 0;
    887 			if (n < P && m < P) { assert(n < SZ(fc)); return fc[n] * ifc[m] * ifc[n - m]; }
    888 			return (!n ? 1 : (*this)(n / P, m / P) * (*this)(n % P, m % P));
    889 		}
    890 		#undef P
    891 	};
    892 	namespace Z {
    893 		const int mod = 998244353;
    894 		using MI = mint<mod>; using math::qpow; Comb<MI> C;
    895 		MI fac(int x) { assert(x >= 0 && x < SZ(C.fc)); return C.fc[x]; }
    896 		MI ifc(int x) { assert(x >= 0 && x < SZ(C.ifc)); return C.ifc[x]; }
    897 		MI inv(int x) { assert(x && x < SZ(C.fc)); return C.ifc[x] * C.fc[x - 1]; }
    898 		MI sab(int x, int y) { return (!y ? !x : C(x + y - 1, y - 1)); }
    899 	}
    900 }
    901 namespace Milkcat {
    902 	using namespace math::Z;
    903 	typedef long long LL;
    904 	typedef pair<LL, LL> pii;
    905 	const int N = 1e7 + 5;
    906 	int n, m, t, v[N]; MI g[N];
    907 	void sieve(int n, int k, MI* f) {
    908 		vector<int> p; fill_n(v + 1, n, 0), f[1] = 1;
    909 		REP(i, 2, n) {
    910 			if (!v[i]) p.pb(i), f[i] = qpow((MI)i, k);
    911 			for (int j : p) {
    912 				if (i * j <= n) f[i * j] = f[i] * f[j], v[i * j] = 1;
    913 				if (i * j > n || i % j == 0) break;
    914 			}
    915 		}
    916 	}
    917 	MI slv2(int n, int m) {
    918 		MI rs = 0;
    919 		REP(i, 0, n - m)
    920 			rs += g[n - i - 1] * C(n - m, i) * (i & 1 ? -1 : 1);
    921 		return rs * (n - 1);
    922 	}
    923 	int main() {
    924 		cin >> t, C.init(1e6);
    925 		while (t --) {
    926 			cin >> n >> m, sieve(n, n - 1, g);
    927 			cout << slv2(n, m) * C(n, m) << '\n';
    928 		}
    929 		return 0;
    930 	}
    931 }
    932 int main() {
    933 	cin.tie(0)->sync_with_stdio(0);
    934 	int T = 1;
    935 	while (T --) Milkcat::main();
    936 	return 0;
    937 }
    938 ```
    939 
    940 ### [Div1E. The end of this world,](https://codeforces.com/contest/2239/problem/E)
    941 
    942 Author: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526")
    943 
    944 **Hint 1**
    945 
    946 Notice that the problem can be transformed as follows: the $i$-th edge appears during the time interval $[\mathrm{low}_i, w_i]$. For each vertex, compute the maximum value of the departure time plus the weight of the destination vertex.
    947 
    948 **Hint 2**
    949 
    950 Consider doing the transitions from back to front.
    951 
    952 **Hint 3**
    953 
    954 We only need to support the following operations:
    955 
    956 * Add and delete edges;
    957 * Query the maximum value in a connected component;
    958 * Take the max of all weights in a connected component with a given number.
    959 
    960 **Hint 4**
    961 
    962 Consider modifying the dynamic graph connectivity approach.
    963 
    964 **Solution**
    965 
    966 Tutorial is loading...
    967 
    968 **Code (by Gold14526)**
    969 
    970 ```
    971 #include<bits/stdc++.h>
    972 #define cint const int
    973 #define uint unsigned int
    974 #define cuint const unsigned int
    975 #define ll long long
    976 #define cll const long long
    977 #define ull unsigned long long
    978 #define cull const unsigned long long
    979 using namespace std;
    980 namespace FastIO
    981 {
    982     const int BUF_SIZE=1<<20;
    983     char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
    984     char* in_ptr=in_buf+BUF_SIZE;
    985     char* out_ptr=out_buf;
    986     char get_char()
    987     {
    988         if(in_ptr==in_buf+BUF_SIZE)
    989         {
    990             in_ptr=in_buf;
    991             fread(in_buf,1,BUF_SIZE,stdin);
    992         }
    993         return *in_ptr++;
    994     }
    995     void put_char(char c)
    996     {
    997         if(out_ptr==out_buf+BUF_SIZE)
    998         {
    999             fwrite(out_buf,1,BUF_SIZE,stdout);
   1000             out_ptr=out_buf;
   1001         }
   1002         *out_ptr++=c;
   1003     }
   1004     struct Flusher
   1005     {
   1006         ~Flusher()
   1007         {
   1008             if(out_ptr!=out_buf)
   1009             {
   1010                 fwrite(out_buf,1,out_ptr-out_buf,stdout);
   1011             }
   1012         }
   1013     } flusher;
   1014 }
   1015 #define getchar FastIO::get_char
   1016 #define putchar FastIO::put_char
   1017 inline int read()
   1018 {
   1019     int x=0;
   1020     bool zf=1;
   1021     char ch=getchar();
   1022     while(ch<'0'||ch>'9')
   1023     {
   1024         if(ch=='-')
   1025         {
   1026             zf=0;
   1027         }
   1028         ch=getchar();
   1029     }
   1030     while(ch>='0'&&ch<='9')
   1031     {
   1032         x=(x<<1)+(x<<3)+(ch^48);
   1033         ch=getchar();
   1034     }
   1035     return zf?x:-x;
   1036 }
   1037 void print(cint x)
   1038 {
   1039     if(x==0)
   1040     {
   1041         putchar('0');
   1042         return;
   1043     }
   1044     char buf[12];
   1045     int len=0,y=x;
   1046     if(y<0)
   1047     {
   1048         putchar('-');
   1049         y=-y;
   1050     }
   1051     while(y)
   1052     {
   1053         buf[len++]=(y%10)+'0';
   1054         y/=10;
   1055     }
   1056     while(len--)
   1057     {
   1058         putchar(buf[len]);
   1059     }
   1060 }
   1061 inline void princh(cint x,const char ch)
   1062 {
   1063     print(x);
   1064     putchar(ch);
   1065 }
   1066 cint N=5e5,M=5e5,H=20;
   1067 int n,m;
   1068 int val[N+1];
   1069 int eu[M+1],ev[M+1],low[M+1],lim[M+1];
   1070 int tl[M+1],tr[M+1];
   1071 struct dx{
   1072     int idx,val;
   1073 }c[M<<1|1];
   1074 struct edge{
   1075     int u,v,l,r;
   1076 };
   1077 vector<edge>E,EL[H+1],ER[H+1];
   1078 struct info{
   1079     int t,u;
   1080 }mdf[M+1];
   1081 int tag[N+(M<<2|1)],mx[N+(M<<2|1)];
   1082 int fa[N+(M<<2|1)];
   1083 int tot;
   1084 int top[N+(M<<2|1)];
   1085 int head[N+(M<<2|1)];
   1086 struct et{
   1087     int to,nxt;
   1088 }ve[M<<2|1];
   1089 int ct;
   1090 inline void add_edge(cint u,cint v)
   1091 {
   1092     ve[++ct]={v,head[u]};
   1093     head[u]=ct;
   1094     ve[++ct]={u,head[v]};
   1095     head[v]=ct;
   1096 }
   1097 inline int newv()
   1098 {
   1099     ++tot;
   1100     tag[tot]=-1;
   1101     mx[tot]=fa[tot]=0;
   1102     return tot;
   1103 }
   1104 struct stck{
   1105     int a[N+1],t;
   1106     inline void clear(){t=0;}
   1107     inline int top(){return a[t];}
   1108     inline void pop(){--t;}
   1109     inline void push(cint x){a[++t]=x;}
   1110     inline bool empty(){return (t==0);}
   1111 }st;
   1112 void dfs(cint u)
   1113 {
   1114     top[u]=u;
   1115     st.clear();
   1116     st.push(u);
   1117     while(!st.empty())
   1118     {
   1119         cint s=st.top();
   1120         st.pop();
   1121         for(int i=head[s];i;i=ve[i].nxt)
   1122         {
   1123             cint v=ve[i].to;
   1124             if(top[v])continue;
   1125             top[v]=u;
   1126             st.push(v);
   1127         }
   1128     }
   1129 }
   1130 void update(cint h,cint l,cint r,vector<edge>&E,int m,cint vl,cint vr)
   1131 {
   1132     if(E.empty())
   1133     {
   1134         for(int i=1;i<=m;++i)
   1135         {
   1136             tag[mdf[i].u]=max(tag[mdf[i].u],mx[mdf[i].u]+c[l].val);
   1137         }
   1138         return;
   1139     }
   1140     cint mid=l+r>>1;
   1141     EL[h].clear();
   1142     ER[h].clear();
   1143     for(int i=vl;i<=vr;++i)
   1144     {
   1145         head[i]=top[i]=fa[i]=0;
   1146     }
   1147     ct=0;
   1148     for(edge &e:E)
   1149     {
   1150         if(e.l<=l&&e.r>=r)
   1151         {
   1152             add_edge(e.u,e.v);
   1153         }
   1154         else
   1155         {
   1156             if(e.l<=mid)EL[h].push_back(e);
   1157             if(e.r>mid)ER[h].push_back(e);
   1158         }
   1159     }
   1160     for(int i=vl;i<=vr;++i)
   1161     {
   1162         if(!top[i])dfs(i);
   1163     }
   1164     if(l==r)
   1165     {
   1166         for(int i=vl;i<=vr;++i)mx[top[i]]=max(mx[top[i]],mx[i]);
   1167         for(int i=1;i<=m;++i)
   1168         {
   1169             cint u=top[mdf[i].u];
   1170             tag[u]=max(tag[u],mx[u]+c[l].val);
   1171         }
   1172         for(int i=vl;i<=vr;++i)
   1173         {
   1174             tag[i]=max(tag[i],tag[top[i]]);
   1175             mx[i]=max(mx[i],mx[top[i]]);
   1176         }
   1177         return;
   1178     }
   1179     cint tmp=tot;
   1180     for(edge &e:ER[h])
   1181     {
   1182         cint u=top[e.u],v=top[e.v];
   1183         if(!fa[u])fa[u]=newv();
   1184         if(!fa[v])fa[v]=newv();
   1185         e.u=fa[u];
   1186         e.v=fa[v];
   1187     }
   1188     int pm=0;
   1189     for(int i=1;i<=m;++i)
   1190     {
   1191         info &p=mdf[i];
   1192         if(p.t>mid)
   1193         {
   1194             cint u=top[p.u];
   1195             if(!fa[u])fa[u]=newv();
   1196             p.u=fa[u];
   1197             swap(p,mdf[++pm]);
   1198         }
   1199     }
   1200     for(int i=vl;i<=vr;++i)
   1201     {
   1202         cint u=fa[top[i]];
   1203         if(u)mx[u]=max(mx[u],mx[i]);
   1204     }
   1205     update(h+1,mid+1,r,ER[h],pm,tmp+1,tot);
   1206     for(int i=vl;i<=vr;++i)
   1207     {
   1208         cint u=fa[top[i]];
   1209         if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);
   1210     }
   1211     tot=tmp;
   1212     for(int i=vl;i<=vr;++i)fa[i]=0;
   1213     for(edge &e:EL[h])
   1214     {
   1215         cint u=top[e.u],v=top[e.v];
   1216         if(!fa[u])fa[u]=newv();
   1217         if(!fa[v])fa[v]=newv();
   1218         e.u=fa[u];
   1219         e.v=fa[v];
   1220     }
   1221     for(int i=pm+1;i<=m;++i)
   1222     {
   1223         info &p=mdf[i];
   1224         cint u=top[p.u];
   1225         if(!fa[u])fa[u]=newv();
   1226         p.u=fa[u];
   1227         swap(p,mdf[i-pm]);
   1228     }
   1229     pm=m-pm;
   1230     for(int i=vl;i<=vr;++i)
   1231     {
   1232         cint u=fa[top[i]];
   1233         if(u)mx[u]=max(mx[u],mx[i]);
   1234     }
   1235     update(h+1,l,mid,EL[h],pm,tmp+1,tot);
   1236     for(int i=vl;i<=vr;++i)
   1237     {
   1238         cint u=fa[top[i]];
   1239         if(u)mx[i]=max(mx[i],mx[u]),tag[i]=max(tag[i],tag[u]);
   1240     }
   1241     tot=tmp;
   1242 }
   1243 void solve()
   1244 {
   1245     tag[0]=-1;
   1246     tot=n=read();
   1247     m=read();
   1248     for(int i=1;i<=n;++i)val[i]=read(),tag[i]=-1,mx[i]=val[i];
   1249     for(int i=1;i<=m;++i)
   1250     {
   1251         eu[i]=read(),ev[i]=read(),lim[i]=read(),low[i]=read();
   1252         c[i]={i,lim[i]};
   1253         c[i+m]={i+m,low[i]};
   1254     }
   1255     sort(c+1,c+(m<<1|1),[&](dx p,dx q){return (p.val==q.val?p.idx>q.idx:p.val<q.val);});
   1256     for(int i=1;i<=(m<<1);++i)
   1257     {
   1258         if(c[i].idx>m)tl[c[i].idx-m]=i;
   1259         else tr[c[i].idx]=i;
   1260     }
   1261     E.clear();
   1262     for(int i=1;i<=m;++i)
   1263     {
   1264         E.push_back({eu[i],ev[i],tl[i],tr[i]});
   1265         mdf[i]={tr[i],eu[i]};
   1266     }
   1267     if(m)update(0,1,m<<1,E,m,1,n);
   1268     for(int i=1;i<=n;++i)princh(tag[i]," \n"[i==n]);
   1269 }
   1270 int main()
   1271 {
   1272     // freopen(".in","r",stdin);
   1273     // freopen(".out","w",stdout);
   1274     int T=read();
   1275     while(T--)solve();
   1276     return 0;
   1277 }
   1278 ```
   1279 
   1280 ### [Div1F. Colorful Works](https://codeforces.com/contest/2239/problem/F)
   1281 
   1282 Author: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009") Preparation: [Milkcat2009](/profile/Milkcat2009 "Grandmaster Milkcat2009")
   1283 
   1284 **Hint 1**
   1285 
   1286 Consider the case where $l_i=0$.
   1287 
   1288 **Hint 2**
   1289 
   1290 Just Consider the most straightforward DP approach, and then try to find some patterns.
   1291 
   1292 **Hint 3**
   1293 
   1294 Try transforming the modulo $2$ counting DP into a game and solve it.
   1295 
   1296 **Hint 4**
   1297 
   1298 You should already know the answer for $l_i=0$; try using the Principle of Inclusion-Exclusion to count.
   1299 
   1300 **Hint 5**
   1301 
   1302 Enumerate which element is strictly greater than half of the total sum.
   1303 
   1304 **Hint 6**
   1305 
   1306 You should already know the $O(nm/w)$ algorithm. Consider that, under modulo $2$, we have $(1+x^k)^2=1+x^{2k}$.
   1307 
   1308 **Solution**
   1309 
   1310 Tutorial is loading...
   1311 
   1312 **Code (by Milkcat2009)**
   1313 
   1314 ```
   1315 #include <bits/stdc++.h>
   1316 #define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
   1317 #define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
   1318 #define CUP(i, l, r) for (int i = (l); i < (r); ++ i)
   1319 #define fi first
   1320 #define se second
   1321 #define pb emplace_back
   1322 #define mems(x, v) memset((x), (v), sizeof(x))
   1323 #define memc(x, y) memcpy((x), (y), sizeof(x))
   1324 #define SZ(x) (int)(x).size()
   1325 #define ALL(x) (x).begin(), (x).end()
   1326 #define ppc(x) __builtin_popcount(x)
   1327 #define ctz(x) __builtin_ctz(x)
   1328 #define clz(x) __builtin_clz(x)
   1329 using namespace std;
   1330 namespace Milkcat {
   1331 	typedef long long LL;
   1332 	typedef pair<LL, LL> pii;
   1333 	const int N = 2e6 + 5, M = 2e5 + 5;
   1334 	int n, m, rs, d, p, q, l[N], r[N], c[M];
   1335 	bitset<M> f;
   1336 	int val(int x) { x -= d; return (x >= 0 && x <= m ? f[x] : 0); }
   1337 	int main() {
   1338 		cin >> n;
   1339 		REP(i, 1, n)
   1340 			cin >> l[i] >> r[i], m = max(m, r[i]);
   1341 		REP(i, 1, n) {
   1342 			if (!l[i]) d = min(d + r[i], (int)1e9);
   1343 			else d = min(d + l[i] - 1, (int)1e9), c[r[i] - l[i] + 1] ++;
   1344 		}
   1345 		f = 1;
   1346 		REP(i, 1, m) {
   1347 			if (i * 2 <= m) c[i * 2] += c[i] >> 1;
   1348 			if (c[i] & 1) f ^= f << i;
   1349 		}
   1350 		REP(i, 2, m) f[i] = f[i] ^ f[i - 2];
   1351 		REP(i, 1, n) {
   1352 			if (!l[i]) rs ^= val(r[i] * 2 - 2), p ^= r[i] & 1;
   1353 			else rs ^= val(l[i] + r[i] - 1 - 2), q += ((l[i] & 1) == (r[i] & 1) ? 1 : 2);
   1354 		}
   1355 		cout << (rs ^ (!q ? !p : (q < 2))) << '\n';
   1356 		REP(i, 1, m) c[i] = 0;
   1357 		m = rs = d = p = q = 0;
   1358 		return 0;
   1359 	}
   1360 }
   1361 int main() {
   1362 	cin.tie(0)->sync_with_stdio(0);
   1363 	int T = 1; cin >> T;
   1364 	while (T --) Milkcat::main();
   1365 	return 0;
   1366 }
   1367 ```