codeforces-scrape

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

1546.md (23833B)


      1 Source: https://codeforces.com/blog/entry/92739
      2 
      3 Tutorial is loading...
      4 
      5 **solution**
      6 
      7 ```
      8 #include<bits/stdc++.h>
      9 using namespace std;
     10 #define O(x) cout<<#x<<" "<<(x)<<"\n"
     11 inline int read(){
     12 	int x=0,f=1,c=getchar();
     13 	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
     14 	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
     15 	return f==1?x:-x;
     16 }
     17 const int N=104;
     18 int n,sum,a[N];
     19 vector<pair<int,int> >ans;
     20 inline void solve(){
     21 	n=read();
     22 	sum=0;
     23 	ans.clear();
     24 	for(int i=1;i<=n;i++)a[i]=read();
     25 	for(int i=1;i<=n;i++){
     26 		a[i]-=read();
     27 		sum+=a[i];
     28 	}
     29 	if(sum){puts("-1");return;}
     30 	for(int i=1;i<=n;i++){
     31 		for(int j=1;j<=a[i];j++){
     32 			for(int k=1;k<=n;k++)if(a[k]<0){
     33 				ans.push_back(make_pair(i,k));
     34 				++a[k];
     35 				break;
     36 			}
     37 		}
     38 	}
     39 	cout<<ans.size()<<"\n";
     40 	for(auto v:ans)cout<<v.first<<" "<<v.second<<"\n";
     41 }
     42 int main(){
     43 	for(int T=read();T--;)solve(); 
     44 	return 0;
     45 }
     46 ```
     47 
     48 Idea: [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka")
     49 
     50 Tutorial is loading...
     51 
     52 **solution**
     53 
     54 ```
     55 #include <cstdio>
     56 const int Maxn=1000000;
     57 char s[Maxn+5];
     58 char ans[Maxn+5];
     59 int n,m;
     60 void solve(){
     61     scanf("%d%d",&n,&m);
     62     n=(n<<1)-1;
     63     for(int i=1;i<=m;i++){
     64         ans[i]=0;
     65     }
     66     for(int i=1;i<=n;i++){
     67         scanf("%s",s+1);
     68         for(int j=1;j<=m;j++){
     69             ans[j]^=s[j];
     70         }
     71     }
     72     for(int i=1;i<=m;i++){
     73         putchar(ans[i]);
     74     }
     75     putchar('\n');
     76 }
     77 int main(){
     78     int T;
     79     scanf("%d",&T);
     80     while(T--){
     81         solve();
     82     }
     83 	return 0;
     84 }
     85 ```
     86 
     87 Idea: [AquaMoon](/profile/AquaMoon "International Master AquaMoon")
     88 
     89 Tutorial is loading...
     90 
     91 **solution**
     92 
     93 ```
     94 #include <bits/stdc++.h>
     95 std::vector<int> a;
     96 int cnt[100001][2];
     97 int main() {
     98   int n, T, flag;
     99   scanf("%d", &T);
    100   while(T--){
    101 	scanf("%d", &n), a.resize(n), flag = 0;
    102     for (int i = 0; i < n; ++i)
    103       scanf("%d", &a[i]), ++cnt[a[i]][i % 2];
    104     std::sort(a.begin(), a.end());
    105     for (int i = 0; i < n; ++i)
    106       --cnt[a[i]][i % 2];
    107     for (int i = 0; i < n; ++i)
    108       if (cnt[a[i]][0] != 0 || cnt[a[i]][1] != 0) {
    109         puts("NO"), flag = 1;
    110 		break;
    111       }
    112     if (flag == 0) puts("YES");
    113 	a.clear();
    114 	for (int i = 0; i < n; ++i)
    115       cnt[a[i]][0] = cnt[a[i]][1] = 0;
    116   }
    117   return 0;
    118 }
    119 ```
    120 
    121 Idea: [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka")
    122 
    123 Tutorial is loading...
    124 
    125 **solution**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129 using namespace std;
    130 
    131 const int MAXN = 100010;
    132 const int MOD = 998244353;
    133 char str[MAXN];
    134 long long F[MAXN], rF[MAXN];
    135 long long inv(long long a, long long m) {
    136 	if (a == 1) return 1;
    137 	return inv(m%a, m) * (m - m/a) % m;
    138 }
    139 int main() {
    140 	int T;
    141 	int n;
    142 	F[0] = rF[0] = 1;
    143 	for (int i = 1; i < MAXN; i++) {
    144 		F[i] = F[i-1] * i % MOD;
    145 		rF[i] = rF[i-1] * inv(i, MOD) % MOD;
    146 	}
    147 	scanf("%d", &T);
    148 	while (T--) {
    149 		scanf("%d", &n);
    150 		scanf("%s", str);
    151 		int cg = 0;
    152 		int c0 = 0;
    153 		int c1 = 0;
    154 		for (int i = 0; i < n; i++) {
    155 			if (str[i] == '0') {
    156 				c0++;
    157 			} else if (i+1 < n && str[i+1] == '1') {
    158 				cg++;
    159 				i++;
    160 			} else {
    161 				c1++;
    162 			}
    163 		}
    164 		long long ans = F[cg + c0] * rF[c0] % MOD * rF[cg] % MOD;
    165 		printf("%d\n", (int) ans);
    166 	}
    167 	return 0;
    168 }
    169 ```
    170 
    171 Idea: [Cirno_9baka](/profile/Cirno_9baka "International Grandmaster Cirno_9baka")
    172 
    173 Tutorial is loading...
    174 
    175 **solution**
    176 
    177 ```
    178 #include<bits/stdc++.h>
    179 using namespace std;
    180 const int maxn=500;
    181 const long long mod=998244353;
    182 typedef pair<int,int> pii;
    183 int n,x,y,s,t;
    184 int a[maxn*2+5][maxn+5],b[maxn+5][maxn+5],f[maxn+5];
    185 vector <pii> v;
    186 vector <int> c[maxn+5][maxn+5];
    187 int main()
    188 {
    189     int T;
    190     scanf("%d",&T);
    191     while (T--)
    192     {
    193         scanf("%d",&n);
    194         for (int i=1;i<=n;i++)
    195         {
    196             for (int j=1;j<=n;j++)
    197             {
    198                 b[i][j]=0;
    199                 c[i][j].clear();
    200             }
    201         }
    202         for (int i=1;i<=n*2;i++)
    203         {
    204             f[i]=0;
    205             for (int j=1;j<=n;j++)
    206             {
    207                 scanf("%d",&a[i][j]);
    208                 b[j][a[i][j]]++;
    209                 c[j][a[i][j]].push_back(i);
    210             }
    211         }
    212         int top=0,tail=0;
    213         int cnt=0,idx=1;
    214         long long ans=1;
    215         v.clear();
    216         for (int i=1;i<=n;i++)
    217         {
    218             for (int j=1;j<=n;j++)
    219             {
    220                 if (b[i][j]==1)
    221                 {
    222                     tail++;
    223                     v.push_back(pii(i,j));
    224                 }
    225             }
    226         }
    227         while (cnt<n)
    228         {
    229             if (top<tail)
    230             {
    231                 x=v[top].first;
    232                 y=v[top].second;
    233                 if (b[x][y]!=1)
    234                 {
    235                     top++;
    236                     continue;
    237                 }
    238                 for (int i=0;i<c[x][y].size();i++)
    239                 {
    240                     if (f[c[x][y][i]]==0)
    241                     {
    242                         t=c[x][y][i];
    243                         break;
    244                     }
    245                 }
    246             }
    247             else
    248             {
    249                 while (f[idx]!=0)
    250                 {
    251                     idx++;
    252                 }
    253                 t=idx;
    254                 ans=ans*2%mod;
    255             }
    256             f[t]=1;
    257             cnt++;
    258             for (int i=1;i<=n;i++)
    259             {
    260                 b[i][a[t][i]]=0;
    261             }
    262             for (int i=1;i<=n;i++)
    263             {
    264                 for (int j=0;j<c[i][a[t][i]].size();j++)
    265                 {
    266                     s=c[i][a[t][i]][j];
    267                     if (f[s]==0)
    268                     {
    269                         f[s]=2;
    270                         for (int k=1;k<=n;k++)
    271                         {
    272                             b[k][a[s][k]]--;
    273                             if (b[k][a[s][k]]==1)
    274                             {
    275                                 tail++;
    276                                 v.push_back(pii(k,a[s][k]));
    277                             }
    278                         }
    279                     }
    280                 }
    281             }
    282             top++;
    283         }
    284         s=0;
    285         printf("%lld\n",ans);
    286         for (int i=1;i<=n*2;i++)
    287         {
    288             if (f[i]==1)
    289             {
    290                 s++;
    291                 if (s<n) printf("%d ",i); else printf("%d\n",i);
    292             }
    293         }
    294     }
    295 }
    296 ```
    297 
    298 Idea: [AquaMoon](/profile/AquaMoon "International Master AquaMoon")
    299 
    300 Tutorial is loading...
    301 
    302 **solution**
    303 
    304 ```
    305 #include<bits/stdc++.h>
    306 using namespace std;
    307 int n,m,i,j,k,ans1,ans2;
    308 long long a[1010][1010];
    309 long long c[1010],x,y,s,t,temp;
    310  
    311 int main()
    312 {
    313     scanf("%d%d",&n,&m);
    314     for (i=0;i<m;i++)
    315     {
    316         for (j=1;j<=n;j++)
    317         {
    318             scanf("%lld",&a[i][j]);
    319             c[i]+=a[i][j];
    320         }
    321     }
    322     x=(c[m-1]-c[0])/(m-1);
    323     for (i=1;i<m;i++)
    324     {
    325         if ((c[i]-c[0])!=x*i)
    326         {
    327             ans1=i;
    328             y=c[i]-c[0]-x*i;
    329             break;
    330         }
    331     }
    332     for (i=1;i<m-1;i++)
    333     {
    334         if (i-1!=ans1&&i!=ans1&&i+1!=ans1)
    335         {
    336             x=0;
    337             for (j=1;j<=n;j++)
    338             {
    339                 x+=a[i-1][j]*a[i-1][j]+a[i+1][j]*a[i+1][j]-a[i][j]*a[i][j]*2;
    340             }
    341             break;
    342         }
    343     }
    344     i=ans1;
    345     t=s=0;
    346     for (j=1;j<=n;j++)
    347     {
    348         s+=a[i-1][j]*a[i-1][j]+a[i+1][j]*a[i+1][j];
    349         t+=a[i][j]*a[i][j]*2;
    350     }
    351     s-=x;
    352     for (j=1;j<=n;j++)
    353     {
    354         temp=t-a[i][j]*a[i][j]*2+(a[i][j]-y)*(a[i][j]-y)*2;
    355         if (temp==s)
    356         {
    357             ans2=a[i][j]-y;
    358             break;
    359         }
    360     }
    361     cout<<ans1<<' '<<ans2<<endl;
    362 }
    363 ```
    364 
    365 Idea: [AquaMoon](/profile/AquaMoon "International Master AquaMoon")
    366 
    367 Tutorial is loading...
    368 
    369 **solution**
    370 
    371 ```
    372 #include<bits/stdc++.h>
    373 using namespace std;
    374 const int N=2000005,E=1000001;
    375 struct str{
    376 	int l;
    377 	long long x;
    378 	int d;
    379 	long long las(){return x+(l-1)*d;}
    380 }a[N];
    381 int ch[N][2],fa[N],h[N],tot,hc,ls[N],siz[N],i;
    382 struct seg{
    383 	int l,r,x;
    384 	bool operator <(const seg &a)const
    385 	{
    386 		return a.r>r;
    387 	}
    388 };
    389 set<seg> p;
    390 void pushup(int i)
    391 {
    392 	siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+a[i].l;
    393 }
    394 void rotate(int x)
    395 {
    396     int y=fa[x];bool d=(ch[y][0]==x);
    397     ch[y][!d]=ch[x][d];
    398     if(ch[x][d]!=0)fa[ch[x][d]]=y;
    399     fa[x]=fa[y];if(fa[y])ch[fa[y]][ch[fa[y]][1]==y]=x;
    400     ch[x][d]=y;fa[y]=x;pushup(y);
    401 }
    402 void splay(int i,int x,int t=0)
    403 {
    404 	for(int y=fa[x];y!=t;rotate(x),y=fa[x])
    405 		if(fa[y]!=t&&(ch[fa[y]][0]==y)==(ch[y][0]==x))
    406 			rotate(y);
    407 	pushup(x);
    408 	h[i]=x;
    409 }
    410 void Findmx(int x)
    411 {
    412 	int i=h[x];
    413 	while(ch[i][1])
    414 		i=ch[i][1];
    415 	splay(x,i);
    416 }
    417 void Findmn(int x)
    418 {
    419 	int i=h[x];
    420 	while(ch[i][0])
    421 		i=ch[i][0];
    422 	splay(x,i);
    423 }
    424 void MMerge(int x,int y)
    425 {
    426 	if(h[y]==0||h[x]==0)
    427 	{
    428 		h[x]=h[y]=max(h[x],h[y]);
    429 		return;
    430 	}
    431 	int i=h[y];
    432 	for(;ch[i][0];i=ch[i][0]);
    433 	ch[i][0]=h[x];
    434 	fa[h[x]]=i;
    435 	splay(y,h[x]);
    436 }
    437 int Merge(int x,int y)
    438 {
    439 	Findmx(x),Findmn(y);
    440 	if(abs(a[h[x]].las()-a[h[y]].x)<=1)
    441 	{
    442 		MMerge(x,y);
    443 		return x;
    444 	}
    445 	if(a[h[x]].las()>a[h[y]].x)
    446 	{
    447 		long long la=a[h[y]].x;
    448 		while(h[x]&&abs(a[h[x]].las()-la)>1)
    449 		{
    450 			if(a[h[x]].d==-1)
    451 				la+=a[h[x]].l;
    452 			else
    453 			{
    454 				if(la+a[h[x]].l<a[h[x]].x)
    455 					la+=a[h[x]].l;
    456 				else
    457 				{
    458 					int li=(a[h[x]].l-a[h[x]].x+la+2)/2;
    459 					la+=a[h[x]].l-li;
    460 					a[h[x]].l=li;
    461 					break;
    462 				}
    463 			}
    464 			h[x]=ch[h[x]][0];
    465 			fa[h[x]]=0;
    466 			Findmx(x);
    467 		}
    468 		h[++hc]=++tot;
    469 		a[tot]={(int)(la-a[h[y]].x),la,-1};
    470 		pushup(tot);
    471 		ls[hc]=ls[x];
    472 		MMerge(x,hc);
    473 		MMerge(hc,y);
    474 	}
    475 	else
    476 	{
    477 		long long la=a[h[x]].las();
    478 		while(h[y]&&abs(a[h[y]].x-la)>1)
    479 		{
    480 			if(a[h[y]].d==1)
    481 				la+=a[h[y]].l;
    482 			else
    483 			{
    484 				if(a[h[y]].las()>la+a[h[y]].l)
    485 					la+=a[h[y]].l;
    486 				else
    487 				{
    488 					int li=(a[h[y]].x-la)/2;
    489 					a[h[y]].x-=li;
    490 					a[h[y]].l-=li;
    491 					la+=li;
    492 					break;
    493 				}
    494 			}
    495 			h[y]=ch[h[y]][1];
    496 			fa[h[y]]=0;
    497 			Findmn(y);
    498 		}
    499 		h[++hc]=++tot;
    500 		a[tot]={(int)(la-a[h[x]].las()),a[h[x]].las()+1,1};
    501 		pushup(tot);
    502 		ls[hc]=ls[x];
    503 		MMerge(x,hc);
    504 		MMerge(hc,y);
    505 	}
    506 	return hc;
    507 }
    508 void Find(int n,int x,int w)
    509 {
    510 	if(w<siz[ch[x][0]])
    511 		Find(n,ch[x][0],w);
    512 	else
    513 		if(siz[ch[x][0]]+a[x].l>w)
    514 		{
    515 			if(siz[ch[x][0]]==w)
    516 			{
    517 				splay(n,x,0);
    518 				return;
    519 			}
    520 			int tmp=ch[x][1];
    521 			ch[x][1]=++tot;
    522 			ch[tot][1]=tmp;
    523 			if(tmp)
    524 				fa[tmp]=tot;
    525 			fa[tot]=x;
    526 			a[tot].l=a[x].l-(w-siz[ch[x][0]]);
    527 			a[x].l=w-siz[ch[x][0]];
    528 			a[tot].x=a[x].x+a[x].d*a[x].l;
    529 			a[tot].d=a[x].d;
    530 			splay(n,tot,0);
    531 			return;
    532 		}
    533 		else
    534 			Find(n,ch[x][1],w-a[x].l-siz[ch[x][0]]);
    535 }
    536 void Update(int l,int x)
    537 {
    538 	if(l==ls[x])
    539 		return;
    540 	int ti=l-ls[x];
    541 	ls[x]=l;
    542 	Findmn(x);
    543 	long long w=a[h[x]].x;
    544 	h[++hc]=++tot;
    545 	a[tot]={ti,w+ti,-1};
    546 	pushup(tot);
    547 	MMerge(hc,x);
    548 	while(1)
    549 	{
    550 		Findmx(x);
    551 		if(ti<a[h[x]].l)
    552 		{
    553 			a[h[x]].l-=ti;
    554 			break;
    555 		}
    556 		ti-=a[h[x]].l;
    557 		h[x]=ch[h[x]][0];
    558 		fa[h[x]]=0;
    559 	}
    560 }
    561 void Add(int ti,int l,int r)
    562 {
    563 	h[++hc]=++tot;
    564 	a[tot]={r-l+1,1<<30,1};
    565 	pushup(tot);
    566 	seg t={l,r,hc};
    567 	ls[hc]=ti;
    568 	auto it=p.lower_bound(t);
    569 	if(it!=p.end()&&it->l==r+1)
    570 	{
    571 		Update(ti,it->x);
    572 		t.x=Merge(t.x,it->x);
    573 		t.r=it->r;
    574 		p.erase(it);
    575 	}
    576 	it=p.lower_bound(t);
    577 	if(it!=p.begin())
    578 	{
    579 		--it;
    580 		if(it->r==l-1)
    581 		{
    582 			Update(ti,it->x);
    583 			t.x=Merge(it->x,t.x);
    584 			t.l=it->l;
    585 			p.erase(it);
    586 		}
    587 	}
    588 	p.insert(t);
    589 }
    590 void Del(int ti,int l,int r)
    591 {
    592 	seg t=*p.lower_bound({l,r,0});
    593 	p.erase(t);
    594 	Update(ti,t.x);
    595 	Find(t.x,h[t.x],l-t.l);
    596 	int u=ch[h[t.x]][0];
    597 	fa[u]=ch[h[t.x]][0]=0;
    598 	pushup(h[t.x]);
    599 	int v=0;
    600 	if(siz[h[t.x]]!=r-l+1)
    601 	{
    602 		Find(t.x,h[t.x],r-l+1);
    603 		v=ch[h[t.x]][0];
    604 		fa[v]=ch[h[t.x]][0]=0;
    605 		v=h[t.x];
    606 	}
    607 	if(l!=t.l)
    608 	{
    609 		h[++hc]=u;
    610 		ls[hc]=ti;
    611 		p.insert({t.l,l-1,hc});
    612 	}
    613 	if(r!=t.r)
    614 	{
    615 		h[++hc]=v;
    616 		ls[hc]=ti;
    617 		p.insert({r+1,t.r,hc});
    618 	}
    619 }
    620 int n,l,r,x,y,u,v,tree[N*4],lazy[N*4];
    621 long long as=1<<30;
    622 struct node{
    623 	int l,r;
    624 };
    625 vector<node> ad[E+5],de[E+5];
    626 void modify(int i,int l,int r,int ll,int rr,int x)
    627 {
    628 	if(l>=ll&&r<=rr)
    629 	{
    630 		lazy[i]+=x;
    631 		tree[i]+=x;
    632 		return;
    633 	}
    634 	int mid=l+r>>1;
    635 	if(mid>=ll)
    636 		modify(i<<1,l,mid,ll,rr,x);
    637 	if(mid<rr)
    638 		modify(i<<1|1,mid+1,r,ll,rr,x);
    639 	tree[i]=max(tree[i<<1],tree[i<<1|1])+lazy[i];
    640 }
    641 int Query(int i,int l,int r,int ll,int rr)
    642 {
    643 	if(l>=ll&&r<=rr)
    644 		return tree[i];
    645 	int mid=l+r>>1,s=0;
    646 	if(mid>=ll)
    647 		s=max(s,Query(i<<1,l,mid,ll,rr));
    648 	if(mid<rr)
    649 		s=max(s,Query(i<<1|1,mid+1,r,ll,rr));
    650 	return s+lazy[i];
    651 }
    652 int Findmx(int i,int l,int r,int ll,int s)
    653 {
    654 	if(s+tree[i]==0)
    655 		return -1;
    656 	if(l==r)
    657 		return l-1;
    658 	int mid=l+r>>1;
    659 	s+=lazy[i];
    660 	if(l>=ll)
    661 	{
    662 		int y=Findmx(i<<1,l,mid,ll,s);
    663 		if(y!=-1)
    664 			return y;
    665 		else
    666 			return Findmx(i<<1|1,mid+1,r,ll,s);
    667 	}
    668 	if(mid>=ll)
    669 	{
    670 		int y=Findmx(i<<1,l,mid,ll,s);
    671 		if(y!=-1)
    672 			return y;
    673 	}
    674 	return Findmx(i<<1|1,mid+1,r,ll,s);
    675 }
    676 int Findmn(int i,int l,int r,int rr,int s)
    677 {
    678 	if(s+tree[i]==0)
    679 		return -1;
    680 	if(l==r)
    681 		return l+1;
    682 	int mid=l+r>>1;
    683 	s+=lazy[i];
    684 	if(r<=rr)
    685 	{
    686 		int y=Findmn(i<<1|1,mid+1,r,rr,s);
    687 		if(y!=-1)
    688 			return y;
    689 		else
    690 			return Findmn(i<<1,l,mid,rr,s);
    691 	}
    692 	if(mid<rr)
    693 	{
    694 		int y=Findmn(i<<1|1,mid+1,r,rr,s);
    695 		if(y!=-1)
    696 			return y;
    697 	}
    698 	return Findmn(i<<1,l,mid,rr,s);
    699 }
    700 void dfs(int i)
    701 {
    702 	if(!i)
    703 		return;
    704 	as=min({as,a[i].x,a[i].las()});
    705 	dfs(ch[i][0]);
    706 	dfs(ch[i][1]);
    707 }
    708 int main()
    709 {
    710 	scanf("%d",&n);
    711 	scanf("%d",&x);
    712 	for(i=1;i<=n;++i)
    713 	{
    714 		scanf("%d %d %d %d",&l,&r,&u,&v);
    715 		--l,++r;
    716 		de[l].push_back({u,v});
    717 		ad[r].push_back({u,v});
    718 	}
    719 	p.insert({0,E*2+5,++hc});
    720 	h[hc]=++tot;
    721 	a[tot]={E*2+5-x+1,0,1};
    722 	ch[tot][0]=2;
    723 	fa[++tot]=1;
    724 	a[tot]={x,x,-1};
    725 	pushup(2);
    726 	pushup(1);
    727 	for(i=0;i<=E+1;++i)
    728 	{
    729 		for(auto it:ad[i])
    730 		{
    731 			modify(1,0,E,it.l,it.r,-1);
    732 			auto ii=p.lower_bound({it.l,it.r,0});
    733 			int nr=ii->l-1;
    734 			--ii;
    735 			int nl=ii->r+1;
    736 			if(nl>nr)
    737 				continue;
    738 			int y=Findmx(1,0,E,nl,0);
    739 			if(y>=nr||y==-1)
    740 				Add(i,nl,nr);
    741 			else
    742 			{
    743 				if(y>=nl)
    744 					Add(i,nl,y);
    745 				int y=Findmn(1,0,E,nr,0);
    746 				if(y<=nr)
    747 					Add(i,y,nr);
    748 			}
    749 		}
    750 		for(auto it:de[i])
    751 		{
    752 			modify(1,0,E,it.l,it.r,1);
    753 			while(1)
    754 			{
    755 				auto y=p.lower_bound({0,it.l,0});
    756 				if(y!=p.end())
    757 				{
    758 					if(min(it.r,y->r)>=max(it.l,y->l))
    759 						Del(i,max(it.l,y->l),min(it.r,y->r));
    760 					else
    761 						break;
    762 				}
    763 				else
    764 					break;
    765 			}
    766 		}
    767 	}
    768 	dfs(h[p.begin()->x]);
    769 	cout<<as;
    770 }
    771 ```
    772 
    773 Idea: [AquaMoon](/profile/AquaMoon "International Master AquaMoon") and [mejiamejia](/profile/mejiamejia "Expert mejiamejia")
    774 
    775 Tutorial is loading...
    776 
    777 **solution**
    778 
    779 ```
    780 // (insert magical incantation)
    781 // (insert offerings for the Gods of codeforces judging servers)
    782 //LXLORZ!!!!//rejudg
    783 #include <bits/stdc++.h>
    784 using namespace std;
    785 
    786 #define MAXN 200005
    787 #define SQRTN 210
    788 
    789 namespace io {
    790 const int __SIZE = (1 << 21) + 1;
    791 char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1,
    792                                            __c, qu[55];
    793 int __f, qr, _eof;
    794 #define Gc()                                                                   \
    795   (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),               \
    796                (iS == iT ? EOF : *iS++))                                       \
    797             : *iS++)
    798 inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
    799 inline void gc(char &x) { x = Gc(); }
    800 inline void pc(char x) {
    801   *oS++ = x;
    802   if (oS == oT)
    803     flush();
    804 }
    805 inline void pstr(const char *s) {
    806   int __len = strlen(s);
    807   for (__f = 0; __f < __len; ++__f)
    808     pc(s[__f]);
    809 }
    810 inline void gstr(char *s) {
    811   for (__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)
    812     __c = Gc();
    813   for (; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc())
    814     *s = __c;
    815   *s = 0;
    816 }
    817 template <class I> inline bool gi(I &x) {
    818   _eof = 0;
    819   for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) {
    820     if (__c == '-')
    821       __f = -1;
    822     _eof |= __c == EOF;
    823   }
    824   for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc())
    825     x = x * 10 + (__c & 15), _eof |= __c == EOF;
    826   x *= __f;
    827   return !_eof;
    828 }
    829 template <class I> inline void print(I x) {
    830   if (!x)
    831     pc('0');
    832   if (x < 0)
    833     pc('-'), x = -x;
    834   while (x)
    835     qu[++qr] = x % 10 + '0', x /= 10;
    836   while (qr)
    837     pc(qu[qr--]);
    838 }
    839 struct Flusher_ {
    840   ~Flusher_() { flush(); }
    841 } io_flusher_;
    842 } // namespace io
    843 using io::gc;
    844 using io::gi;
    845 using io::gstr;
    846 using io::pc;
    847 using io::print;
    848 using io::pstr;
    849 
    850 #define all(a) a.begin(), a.end()
    851 #define fi first
    852 #define se second
    853 #define pb push_back
    854 #define mp make_pair
    855 
    856 using ll = long long;
    857 using pii = pair<int, int>;
    858 
    859 int n;
    860 int a[MAXN], X[MAXN], Y[MAXN];
    861 
    862 int Xa[MAXN], Ya[MAXN];
    863 
    864 int dyn[SQRTN + 5];
    865 bool dynp[MAXN];
    866 
    867 int ps1[MAXN];
    868 ll ps2[MAXN];
    869 
    870 ll ps_7j[MAXN];
    871 
    872 int fake_a[MAXN], fake_Xa[MAXN], fake_Ya[MAXN];
    873 
    874 // TODO: replace with linked list
    875 
    876 struct offl {
    877   int val, id, nxt;
    878 } detecpool[(SQRTN * SQRTN * 11) / 2 + 5];
    879 
    880 int detec[MAXN];
    881 // int detec7[MAXN];
    882 int detec8f[MAXN];
    883 int detecX[MAXN], detecY[MAXN];
    884 
    885 int dryans[(SQRTN * SQRTN * 3) / 2 + 5];
    886 int dryansX[(SQRTN * SQRTN) / 2 + 5];
    887 int dryansY[(SQRTN * SQRTN * 4) / 2 + 5];
    888 ll dryans_7[(SQRTN * SQRTN) / 2 + 5];
    889 ll dryans_8_former[(SQRTN * SQRTN * 2) / 2 + 5];
    890 ll ijk_static[MAXN];
    891 
    892 void dryrun(vector<pii> ops) {
    893   copy(a, a + n, fake_a);
    894   copy(Xa, Xa + n, fake_Xa);
    895   copy(Ya, Ya + n, fake_Ya);
    896   memset(detec, -1, sizeof detec);
    897   memset(detecX, -1, sizeof detecX);
    898   memset(detecY, -1, sizeof detecY);
    899   // memset(detec7, -1, sizeof detec7);
    900   memset(detec8f, -1, sizeof detec8f);
    901   int pooln = 0;
    902   auto push_back = [&](int *ve, int pos, int va, int id) {
    903     detecpool[pooln] = {va, id, ve[pos]};
    904     ve[pos] = pooln;
    905     pooln++;
    906   };
    907   int dryid = 0, dryidX = 0, dryidY = 0, dryid7 = 0, dryid8f = 0;
    908   for (auto [opn, r] : ops) {
    909     if (opn != -1) {
    910       assert(dynp[opn]);
    911       a[opn] = r;
    912       Xa[opn] = X[r];
    913       Ya[opn] = Y[r];
    914     } else {
    915       int mxdyn = 0;
    916       for (int i = 0; dyn[i] <= r; i++)
    917         mxdyn++;
    918       for (int _j = 0; _j < mxdyn; _j++) {
    919         int j = dyn[_j];
    920         int pfx_xai_km1 = 0;
    921         if (j != 0) {
    922           // int pfx_ixaj_jm1 = dryans[dryid++];
    923           // int pfx_iyaj_r = dryans[dryid++];
    924           // int pfx_iyaj_j = dryans[dryid++];
    925           push_back(detecX, j - 1, a[j], dryidX++);
    926           push_back(detecY, r, a[j], dryidY++);
    927           push_back(detecY, j, a[j], dryidY++);
    928 
    929           int k = dyn[_j];
    930           // pfx_xai_km1 = dryans[dryid++];
    931           // int pfx_yak_km1 = dryans[dryid++];
    932           push_back(detec, k - 1, Xa[k], dryid++);
    933           push_back(detec, k - 1, Ya[k], dryid++);
    934 
    935           // ll pfx_yak_km1 = dryans_7[dryid7++];
    936           // push_back(detec7, k - 1, Ya[k], dryid7++);
    937         }
    938         int i = j;
    939         if (i != r) {
    940           // ll sfx_xai_ip1 = dryans_8_former[dryid8f++];
    941           // ll sfx_xai_rp1 = dryans_8_former[dryid8f++];
    942           // int pfx_xai_r = dryans[dryid++];
    943           // int pfx_xai_i = pfx_xai_km1;
    944           // int pfx_iyxai_n = dryans[dryid++];
    945           // int pfx_iyxai_r = dryans[dryid++];
    946           push_back(detec8f, i + 1, Xa[i], dryid8f++);
    947           push_back(detec8f, r + 1, Xa[i], dryid8f++);
    948           push_back(detec, r, Xa[i], dryid++);
    949           push_back(detecY, n, Xa[i], dryidY++);
    950           push_back(detecY, r, Xa[i], dryidY++);
    951         }
    952       }
    953     }
    954   }
    955   for (int i = 0; i <= n; i++) {
    956     if (i != n && !dynp[i]) {
    957       ps1[a[i]]++;
    958     }
    959     for (int pid = detec[i]; pid != -1; pid = detecpool[pid].nxt)
    960       dryans[detecpool[pid].id] = ps1[detecpool[pid].val];
    961   }
    962   memset(ps1, 0, n * (sizeof(int)));
    963   ll cpsm = 0;
    964   for (int i = 0; i <= n; i++) {
    965     if (i != n && !dynp[i]) {
    966       cpsm += ps_7j[Ya[i]];
    967       ps_7j[a[i]] += ps1[a[i]];
    968       ps1[Xa[i]]++;
    969     }
    970     ijk_static[i] = cpsm;
    971     for (int pid = detecX[i]; pid != -1; pid = detecpool[pid].nxt) {
    972       dryansX[detecpool[pid].id] = ps1[detecpool[pid].val];
    973       dryans_7[detecpool[pid].id] = ps_7j[Y[detecpool[pid].val]];
    974     }
    975   }
    976   memset(ps1, 0, n * (sizeof(int)));
    977   for (int i = 0; i <= n; i++) {
    978     if (i != n && !dynp[i]) {
    979       ps1[Ya[i]]++;
    980     }
    981     for (int pid = detecY[i]; pid != -1; pid = detecpool[pid].nxt)
    982       dryansY[detecpool[pid].id] = ps1[detecpool[pid].val];
    983   }
    984   memset(ps1, 0, n * (sizeof(int)));
    985   memset(ps_7j, 0, n * (sizeof(ll)));
    986 
    987   for (int i = n; i >= 0; i--) {
    988     if (i != n && !dynp[i]) {
    989       ps2[a[i]] += ps1[a[i]];
    990       ps1[Ya[i]]++;
    991     }
    992     for (int pid = detec8f[i]; pid != -1; pid = detecpool[pid].nxt)
    993       dryans_8_former[detecpool[pid].id] = ps2[detecpool[pid].val];
    994   }
    995   memset(ps1, 0, n * (sizeof(int)));
    996   memset(ps2, 0, n * (sizeof(ll)));
    997   copy(fake_a, fake_a + n, a);
    998   copy(fake_Xa, fake_Xa + n, Xa);
    999   copy(fake_Ya, fake_Ya + n, Ya);
   1000 }
   1001 
   1002 int PfxGud3[MAXN], SfxGud4[MAXN];
   1003 
   1004 void process(vector<pii> ops) {
   1005   set<int> mdfd;
   1006   for (auto [xx, b] : ops)
   1007     if (xx != -1)
   1008       mdfd.insert(xx);
   1009   int dync = 0;
   1010   memset(dyn, 1, sizeof dyn);
   1011   for (int i : mdfd)
   1012     dyn[dync++] = i;
   1013   memset(dynp, 0, sizeof dynp);
   1014   for (int i = 0; i < dync; i++)
   1015     dynp[dyn[i]] = 1;
   1016   dryrun(ops);
   1017   int dryid = 0, dryidX = 0, dryidY = 0, dryid6l = 0, dryid7 = 0, dryid8f = 0;
   1018   for (auto [opn, r] : ops) {
   1019     if (opn != -1) {
   1020       a[opn] = r;
   1021       Xa[opn] = X[r];
   1022       Ya[opn] = Y[r];
   1023     } else {
   1024       int mxdyn = 0;
   1025       for (int i = 0; dyn[i] <= r; i++)
   1026         mxdyn++;
   1027       ll P1 = ijk_static[r], P2 = 0, P3 = 0, P4 = 0, P5 = 0, P6 = 0, P7 = 0,
   1028          P8 = 0;
   1029       for (int _i = 0; _i < mxdyn; _i++) {
   1030         int i = dyn[_i];
   1031         PfxGud3[i] = ps1[a[i]];
   1032         P2 += ps2[Ya[i]];
   1033         ps2[a[i]] += ps1[a[i]];
   1034         ps1[Xa[i]]++;
   1035       }
   1036       for (int _i = 0; _i < mxdyn; _i++) {
   1037         int i = dyn[_i];
   1038         ps2[a[i]] = 0;
   1039         ps1[Xa[i]] = 0;
   1040       }
   1041       for (int _i = mxdyn - 1; _i >= 0; _i--) {
   1042         int i = dyn[_i];
   1043         SfxGud4[i] = ps1[a[i]];
   1044         ps1[Ya[i]]++;
   1045       }
   1046       for (int _i = 0; _i < mxdyn; _i++) {
   1047         int i = dyn[_i];
   1048         ps1[Ya[i]] = 0;
   1049       }
   1050       for (int _j = 0; _j < mxdyn; _j++) {
   1051         int j = dyn[_j];
   1052         int pfx_xai_km1 = 0;
   1053         if (j != 0) {
   1054           int pfx_ixaj_jm1 = dryansX[dryidX++];
   1055           int pfx_iyaj_r = dryansY[dryidY++];
   1056           int pfx_iyaj_j = dryansY[dryidY++];
   1057           P3 += PfxGud3[j] * (pfx_iyaj_r - pfx_iyaj_j);
   1058           P4 += pfx_ixaj_jm1 * SfxGud4[j];
   1059           P5 += 1ll * pfx_ixaj_jm1 * (pfx_iyaj_r - pfx_iyaj_j);
   1060 
   1061           int k = dyn[_j];
   1062           pfx_xai_km1 = dryans[dryid++];
   1063           int pfx_yak_km1 = dryans[dryid++];
   1064           int pfxDyn_ixyak = ps1[Ya[k]];
   1065           ll pfxDyn_BAD_ixyak = ps2[Ya[k]];
   1066           ps1[Xa[k]]++;
   1067           ps2[Xa[k]] += pfx_xai_km1;
   1068           P6 += 1ll * pfx_yak_km1 * pfxDyn_ixyak - pfxDyn_BAD_ixyak;
   1069 
   1070           P7 += dryans_7[dryid7++];
   1071         } else {
   1072           ps1[Xa[j]]++;
   1073         }
   1074         int i = j;
   1075         if (i != r) {
   1076           ll sfx_xai_ip1 = dryans_8_former[dryid8f++];
   1077           ll sfx_xai_rp1 = dryans_8_former[dryid8f++];
   1078           int pfx_xai_r = dryans[dryid++];
   1079           int pfx_xai_i = pfx_xai_km1;
   1080           int pfx_iyxai_n = dryansY[dryidY++];
   1081           int pfx_iyxai_r = dryansY[dryidY++];
   1082           P8 += (sfx_xai_ip1 - sfx_xai_rp1) -
   1083                 1ll * (pfx_xai_r - pfx_xai_i) * (pfx_iyxai_n - pfx_iyxai_r);
   1084         }
   1085       }
   1086       for (int _i = 0; _i < mxdyn; _i++) {
   1087         int i = dyn[_i];
   1088         ps2[Xa[i]] = 0;
   1089         ps1[Xa[i]] = 0;
   1090       }
   1091       print(P1 + P2 + P3 + P4 + P5 + P6 + P7 + P8);
   1092       pc('\n');
   1093     }
   1094   }
   1095 }
   1096 
   1097 signed main() {
   1098   ios_base::sync_with_stdio(false);
   1099   cin.tie(0);
   1100   int m;
   1101   gi(n), gi(m);
   1102   for (int i = 0; i < n; i++) {
   1103     gi(a[i]);
   1104     a[i]--;
   1105   }
   1106   for (int i = 0; i < n; i++) {
   1107     gi(X[i]);
   1108     X[i]--;
   1109   }
   1110   for (int i = 0; i < n; i++) {
   1111     gi(Y[i]);
   1112     Y[i]--;
   1113   }
   1114   for (int i = 0; i < n; i++) {
   1115     Xa[i] = X[a[i]];
   1116     Ya[i] = Y[a[i]];
   1117   }
   1118   vector<pii> opq;
   1119   for (int qx = 0; qx < m; qx++) {
   1120     int op, v;
   1121     gi(op);
   1122     gi(v);
   1123     if (op == 1) {
   1124       int r;
   1125       gi(r);
   1126       opq.push_back({v - 1, r - 1});
   1127     } else {
   1128       opq.push_back({-1, v - 1});
   1129     }
   1130     if (opq.size() == SQRTN) {
   1131       process(opq);
   1132       opq.clear();
   1133     }
   1134   }
   1135   process(opq);
   1136 }
   1137 ```
   1138 
   1139 Idea: [ODT](/profile/ODT "Master ODT") and [box](/profile/box "International Master box")
   1140 
   1141 **UPD:** Chinese editorial can be found [here](https://www.cnblogs.com/invisible-eyes/p/15003033.html).