QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408552#8226. 堆操作练习题2xuqin50 755ms62196kbC++143.6kb2024-05-10 17:10:272024-05-10 17:10:29

Judging History

你现在查看的是最新测评结果

  • [2024-05-22 20:40:58]
  • hack成功,自动添加数据
  • (/hack/631)
  • [2024-05-10 17:10:29]
  • 评测
  • 测评结果:50
  • 用时:755ms
  • 内存:62196kb
  • [2024-05-10 17:10:27]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<random>
#include<chrono>
#include<bitset>
#include<map>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#define eb emplace_back

using namespace std;
const int maxn=(1<<18)+10, maxm=11+10, inf=2e9+10, P=1e9+7;
const double eps=1e-10, pi=acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
const LL INF=4e18;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, LL> pll;
inline int read() {
	int x=0, f=1; char c=getchar();
	for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
	for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
	return f?x:-x;
}
mt19937 rnd((unsigned)chrono::steady_clock::now().time_since_epoch().count());
inline int ksm(int x, int y) {
	int s=1;
	for(; y; y>>=1, x=1LL*x*x%P)
		if(y&1) s=1LL*s*x%P;
	return s;
}
inline int add(int x, int y) {x+=y; return x>=P?x-P:x;}
inline int del(int x, int y) {x-=y; return x<0?x+P:x;}
LL gcd(LL x, LL y) {return y?gcd(y, x%y):x;}

int h, a[maxn], b[maxn], rk[20][maxn], dep[maxn], val[20][maxn];

inline int down(int x) {
	a[x]=0;
	while(x+x<(1<<h)) {
		if(a[x<<1]==0&&a[x<<1|1]==0) break;
		if(a[x<<1]<a[x<<1|1]) swap(a[x], a[x<<1|1]), x=(x<<1|1);
			else swap(a[x], a[x<<1]), x=(x<<1);
	}
	return x;
}
int tr[2][20][maxn];
inline void modify(int bel, int p, int id, int u, int t) {//id start from 0
	for(int i=u; i<(1<<(h-p+1)); i+=(i&(-i))) 
		tr[bel][p][i+id*((1<<(h-p+1))-1)]+=t;
}
inline int getsum(int bel, int p, int id, int u) {
	int s=0;
	for(int i=u; i>0; i-=(i&(-i))) s+=tr[bel][p][i+id*((1<<(h-p+1))-1)];
	return s;
}

int pos[1000010], pw[maxn];
int main() {
	h=read();
	for(int i=1; i<(1<<h); ++i) a[i]=b[i]=read(), dep[i]=dep[i>>1]+1, pos[a[i]]=i;
	sort(b+1, b+(1<<h));
	for(int i=1; i<(1<<h); ++i) a[i]=lower_bound(b+1, b+(1<<h), a[i])-b;
	for(int i=1; i<(1<<h); ++i) b[i]=a[i];
	for(int p=1; p<=h; ++p) {
		for(int i=1; i<(1<<h); ++i) a[i]=b[i];
		for(int i=(1<<(p-1)); i<(1<<p); ++i) {
			for(int j=1; j<(1<<(h-p+1)); ++j) {
				val[p][a[i]]=j;
				int x=down(i);
				rk[p][x]=j; 
			}
		}
		//for(int i=1; i<(1<<h); ++i)
		//	if(rk[p][i]>0)
		//		printf("rk[%d][%d]=%d\n", p, i, rk[p][i]);
		//for(int i=1; i<(1<<h); ++i)
		//	if(val[p][i]>0)
		//		printf("val[%d][%d]=%d\n", p, i, val[p][i]);
	}
	for(int p=1; p<=h; ++p) {
		for(int x=1; x<(1<<h); ++x)
			if(rk[p][x]!=0&&rk[p][x>>1]!=0)
				rk[p][x]=min(rk[p][x], rk[p][x>>1]);
	}
	int q=read();
	pw[0]=1;
	for(int i=1; i<(1<<h); ++i) pw[i]=2LL*pw[i-1]%P;
	while(q--) {
		int ty=read(), x=read(), y=read();
		if(ty==1) {
			--y; int t=x;
			while(x) {
				modify(y, dep[x], x-(1<<(dep[x]-1)), rk[dep[x]][t], 1);
				x>>=1;
			}
		} else if(ty==2) {
			--y; int t=x;
			while(x) {
				modify(y, dep[x], x-(1<<(dep[x]-1)), rk[dep[x]][t], -1);
				x>>=1;
			}
		} else if(ty==3) {
			if(pos[y]==0) {puts("0"); continue;}
			y=val[dep[x]][b[pos[y]]];
		//	printf("y=%d\n", y);
			if(y==0) {puts("0"); continue;}
			int t=getsum(0, dep[x], x-((1<<(dep[x]-1))), y-1);
		//	printf("t=%d\n", t);
			if(t>0) {puts("0"); continue;}
			t=getsum(0, dep[x], x-((1<<(dep[x]-1))), y);
		//	printf("t=%d\n", t);
		//	printf("o=%d\n", getsum(1, dep[x], x-((1<<(dep[x]-1))), y)-getsum(1, dep[x], x-((1<<(dep[x]-1))), y-1));
			if(t+getsum(1, dep[x], x-((1<<(dep[x]-1))), y)-getsum(1, dep[x], x-((1<<(dep[x]-1))), y-1)==1) {
				printf("%d\n", pw[getsum(1, dep[x], x-((1<<(dep[x]-1))), (1<<(h-dep[x]+1))-1)-getsum(1, dep[x], x-((1<<(dep[x]-1))), y)]);
			} else puts("0");
		}
	}
	return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 3752kb

input:

2
3 2 1
50
3 3 1
1 1 2
1 2 1
2 2 1
1 2 2
2 1 2
1 1 1
1 3 2
2 1 1
2 2 2
3 1 2
3 1 3
2 3 2
1 3 2
1 2 2
2 2 2
1 2 1
1 1 2
3 1 1
2 1 2
1 1 1
2 1 1
3 1 2
3 1 3
2 3 2
1 3 2
2 2 1
1 2 1
1 1 1
3 1 2
2 1 1
1 1 1
3 3 1
2 1 1
2 3 2
1 3 1
2 3 1
1 1 2
3 1 3
2 1 2
3 3 1
3 1 3
3 1 1
3 1 1
1 3 2
1 1 1
2 1 1
3 1 1
2...

output:

0
1
0
0
0
2
0
1
2
0
1
0
0
0
0

result:

ok 15 numbers

Test #2:

score: 10
Accepted
time: 0ms
memory: 3896kb

input:

2
3 1 2
50
1 2 2
3 3 2
2 2 2
1 3 1
1 1 1
3 3 2
2 1 1
3 1 3
2 3 1
1 3 1
1 1 1
1 2 2
2 1 1
3 1 3
2 3 1
2 2 2
1 1 2
1 2 1
1 3 1
2 1 2
3 3 2
1 1 1
2 3 1
1 3 2
2 3 2
1 3 1
2 2 1
3 3 2
3 1 1
2 3 1
2 1 1
1 3 1
2 3 1
3 1 3
3 1 3
3 1 3
1 1 1
2 1 1
3 1 2
1 2 1
3 1 1
3 3 2
3 1 3
2 2 1
1 1 1
2 1 1
1 2 1
1 1 2
2...

output:

0
1
1
2
1
1
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 3828kb

input:

4
15 14 13 9 10 11 12 2 7 4 5 1 6 8 3
500
3 1 15
3 1 13
1 9 1
1 6 2
1 15 2
1 14 1
1 10 2
1 5 2
3 12 1
1 1 1
1 4 1
3 6 6
3 10 4
1 3 1
3 13 6
1 11 2
2 4 1
2 14 1
3 6 6
3 1 11
3 1 14
3 2 4
2 6 2
2 15 2
3 1 9
3 7 12
1 13 2
2 9 1
2 5 2
3 14 8
1 15 2
1 12 1
3 11 5
1 5 2
3 1 15
3 5 10
3 1 11
1 14 1
2 13 2
...

output:

0
0
0
0
1
0
0
8
0
0
0
0
0
1
16
4
0
0
0
8
0
0
1
8
0
0
16
0
0
0
0
4
0
0
0
0
1
0
0
0
0
0
8
1
0
128
0
0
0
2
1
16
0
64
4
0
0
0
2
1
2
0
1
0
0
0
0
2
1
16
0
0
1
0
1
4
0
0
2
0
2
0
0
2
4
0
1
0
1
1
0
4
0
0
0
0
1
0
0
0
1
0
0
0
0
0
4
1
0
0
0
1
1
0
0
0
0
1
1
4
0
1
1
1
1
0
1
1
1
1
0
0
4
0
0
0
0
0
0
1
2
1
2
1
0
4
0...

result:

wrong answer 5th numbers differ - expected: '8', found: '1'

Subtask #3:

score: 20
Accepted

Test #5:

score: 20
Accepted
time: 1ms
memory: 3912kb

input:

9
511 509 510 504 507 505 508 501 503 506 502 494 500 499 493 473 483 495 475 491 497 461 487 490 489 498 496 478 485 480 488 378 469 482 477 462 448 422 470 424 467 421 492 439 454 484 451 376 385 458 464 463 486 411 472 449 474 459 468 479 413 457 455 371 315 432 437 466 453 476 418 433 363 434 38...

output:

0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
1
1
1
0
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
0
0
1
1
1
1
1
0
0
1
1
1
1
1
0
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
1
1
1
0
0
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
1
1
...

result:

ok 1644 numbers

Test #6:

score: 20
Accepted
time: 1ms
memory: 3864kb

input:

9
511 510 506 509 508 505 504 500 507 501 503 497 498 502 484 454 495 485 494 488 496 493 474 491 460 487 490 486 499 468 467 408 448 451 469 479 478 412 492 482 476 440 466 489 411 462 470 384 407 438 452 430 464 439 481 456 483 449 422 420 446 441 370 372 376 404 443 369 417 405 416 465 444 275 45...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
1
1
0
1
0
1
0
0
1
0
1
0
1
1
1
1
0
1
1
0
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
0
0
0
0
1
...

result:

ok 1657 numbers

Test #7:

score: 20
Accepted
time: 1ms
memory: 3864kb

input:

9
511 508 510 502 505 506 509 497 489 501 504 496 500 507 499 494 486 466 482 472 442 503 453 492 469 481 477 488 491 483 484 493 416 480 485 420 465 436 471 353 447 437 384 490 498 399 381 487 468 461 457 478 479 474 473 248 430 412 448 429 421 449 475 423 476 338 410 435 444 438 462 379 415 372 39...

output:

0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
0
1
0
1
1
1
0
0
1
0
0
1
0
0
1
1
1
1
0
1
1
0
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
0
0
0
1
0
0
0
0
1
0
1
1
0
1
1
0
1
0
0
0
1
0
1
1
1
0
1
0
0
1
1
0
1
1
0
1
1
0
0
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
...

result:

ok 1644 numbers

Test #8:

score: 20
Accepted
time: 1ms
memory: 4024kb

input:

9
511 509 510 505 506 508 490 499 484 497 501 507 504 477 481 494 469 479 468 458 486 496 487 503 495 498 449 461 467 476 480 448 470 424 459 413 478 441 466 429 446 485 438 489 463 473 483 502 500 491 492 474 493 443 430 385 433 453 447 460 472 379 408 363 415 367 445 401 405 426 259 383 351 322 45...

output:

0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
0
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
1
0
1
1
...

result:

ok 1620 numbers

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 20
Accepted

Dependency #3:

100%
Accepted

Test #13:

score: 20
Accepted
time: 747ms
memory: 62196kb

input:

18
262143 262142 262141 262135 262134 262140 262137 262119 262122 262133 262117 262136 262139 262129 262130 262114 262088 262099 262080 262126 262131 262091 262101 262128 262132 262138 262115 262103 262121 262069 262094 262111 262078 261968 262042 262032 262097 262059 262074 262086 262113 262124 262...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
...

result:

ok 166527 numbers

Test #14:

score: 20
Accepted
time: 755ms
memory: 62176kb

input:

18
262143 262141 262142 262139 262135 262140 262136 262138 262126 262129 262130 262132 262134 262122 262118 262137 262082 262090 262083 262103 262112 262121 262123 262131 262128 262133 262127 262105 262111 262085 262106 262124 262125 262066 262080 262055 262048 262069 261865 262096 262102 262068 262...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 166874 numbers

Test #15:

score: 20
Accepted
time: 749ms
memory: 62196kb

input:

18
262143 262141 262142 262135 262139 262134 262140 262123 262120 262130 262125 262128 262127 262138 262136 262108 262102 262077 262112 262099 262122 262117 262124 262113 262116 262126 262110 262137 262104 262131 262121 262039 262092 262035 262078 262004 262073 262109 262106 262087 262046 262076 262...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 166762 numbers

Test #16:

score: 20
Accepted
time: 734ms
memory: 62180kb

input:

18
262143 262141 262142 262133 262140 262138 262137 262130 262125 262135 262139 262117 262136 262120 262124 262083 262128 262086 262118 262129 262131 262116 262121 262097 262115 262127 262134 262103 262107 262122 262119 262077 262044 262114 262042 262081 262053 262079 262109 262101 262108 262070 262...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
...

result:

ok 166661 numbers

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%