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).