QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#749470#7495. 世上最幸福的女孩TheZone0 35ms54740kbC++203.6kb2024-11-15 01:13:102024-11-15 01:13:12

Judging History

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

  • [2024-11-15 01:13:12]
  • 评测
  • 测评结果：0
  • 用时：35ms
  • 内存：54740kb
查看
  • [2024-11-15 01:13:10]
  • 提交

answer

#include<bits/stdc++.h> 
using namespace std;
#define MAXN 200005
#define MAXM 6000005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int lim=200000;
const int n1=500;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
const int M=lim/n1+5;
int n,m,a[MAXN],ch[MAXM][2],siz[MAXM],summ[MAXM][31][2],tot;
int sum[MAXN][31][2],lzy,cnt,rev[MAXM],pow2[31],ord[31],sumt;
LL ans;
void pushdown(int rt,int dp){
	int lim=(1<<dp)-1;if(!(rev[rt]&lim))return ;
	if(ch[rt][0])rev[ch[rt][0]]^=rev[rt];
	if(ch[rt][1])rev[ch[rt][1]]^=rev[rt];
	if(rev[rt]&(1<<dp-1))swap(ch[rt][0],ch[rt][1]);
	for(int i=0;i<dp-1;i++)if((rev[rt]>>i)&1)
		swap(summ[ch[rt][0]][i][0],summ[ch[rt][0]][i][1]),
		swap(summ[ch[rt][1]][i][0],summ[ch[rt][1]][i][1]);
	rev[rt]=0;
}
LL query(int rt,int k,int dp){
	if(k==0||dp==0||!rt)return 0;LL res=0;pushdown(rt,dp);
	if(!ord[dp-1]){
		if(siz[ch[rt][0]]<=k){
			res+=query(ch[rt][1],k-siz[ch[rt][0]],dp-1);
			res+=1ll*(k-siz[ch[rt][0]])*pow2[dp-1];
			for(int i=0;i<dp-1;i++) 
				res+=1ll*pow2[i]*summ[ch[rt][0]][i][1];
		}
		else res+=query(ch[rt][0],k,dp-1);
	}
	else{
		if(siz[ch[rt][1]]<=k){
			res+=query(ch[rt][0],k-siz[ch[rt][1]],dp-1);
			res+=1ll*siz[ch[rt][1]]*pow2[dp-1];
			for(int i=0;i<dp-1;i++)
				res+=1ll*pow2[i]*summ[ch[rt][1]][i][1];
		}
		else res+=query(ch[rt][1],k,dp-1)+1ll*k*pow2[dp-1];
	}
	return res;
}
void insert(int &rt,int dp,int aw){
	if(!rt)rt=++cnt;siz[rt]++;
	for(int j=0;j<30;j++)summ[rt][j][(aw>>j)&1]++;
	if(dp==0)return ;pushdown(rt,dp);
	insert(ch[rt][(aw>>dp-1)&1],dp-1,aw);
}
signed main(){
	read(n);int root=++cnt;
	pow2[0]=1;for(int i=1;i<30;i++)pow2[i]=pow2[i-1]+pow2[i-1];
	for(int i=1,x;i<=n;i++){
		read(x),a[++tot]=x;
		for(int j=0;j<30;j++)
			sum[tot][j][0]=sum[tot-1][j][0],
			sum[tot][j][1]=sum[tot-1][j][1],
			sum[tot][j][(x>>j)&1]++;
	}
	read(m);
	for(int i=1;i<=m;i++){
		int opt;read(opt);
		if(opt==1){
			int x;read(x);a[++tot]=x^lzy;
			for(int j=0;j<30;j++)
				sum[tot][j][0]=sum[tot-1][j][0],
				sum[tot][j][1]=sum[tot-1][j][1],
				sum[tot][j][(a[tot]>>j)&1]++;
		}
		if(opt==2){
			int l,r;read(l);read(r);ans=0;
			if(l<=sumt)ans+=query(root,min(r,sumt),30)-query(root,l-1,30);
			if(r>sumt){
				int al=max(1,l-sumt),ar=r-sumt;
				for(int j=0;j<30;j++){
					int t=((lzy>>j)&1)^1;
					ans+=1ll*pow2[j]*(sum[ar][j][t]-sum[al-1][j][t]);
				}
			}
			printf("%lld\n",ans);
		}
		if(opt==3){
			int x;read(x);lzy^=x;
			for(int j=0;j<30;j++)if((x>>j)&1)
				swap(summ[root][j][0],summ[root][j][1]),ord[j]^=1;
			rev[root]^=x;
		}
		if(opt==4){
			for(int j=0;j<30;j++)ord[j]=0;
			for(int j=1;j<=tot;j++)insert(root,30,a[j]^lzy),a[j]=0;
			sumt+=tot;tot=lzy=0;
		}
	}
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 54244kb

input:

300000 600000
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36 -37 -38 -39 -40 -41 -42 -43 -44 -45 -46 -47 -48 -49 -50 -51 -52 -53 -54 -55 -56 -57 -58 -59 -60 -61 -62 -63 -64 -65 -66 -67 -68 -69 -70 -71 -72 -73 -74...

output:

result:

wrong answer Answer contains longer sequence [length = 300007], but output contains 0 elements

Test #2:

score: 0
Wrong Answer
time: 17ms
memory: 52760kb

input:

300000 600000
-6000 -12000 -18000 -24000 -30000 -36000 -42000 -48000 -54000 -60000 -66000 -72000 -78000 -84000 -90000 -96000 -102000 -108000 -114000 -120000 -126000 -132000 -138000 -144000 -150000 -156000 -162000 -168000 -174000 -180000 -186000 -192000 -198000 -204000 -210000 -216000 -222000 -228000...

output:

result:

wrong answer Answer contains longer sequence [length = 300188], but output contains 0 elements

Test #3:

score: 0
Wrong Answer
time: 11ms
memory: 52964kb

input:

300000 600000
694739332 12000 18000 24000 30000 36000 42000 48000 54000 60000 66000 72000 78000 84000 90000 96000 102000 108000 114000 120000 126000 132000 138000 805133449 150000 156000 162000 168000 174000 180000 186000 192000 198000 204000 210000 216000 222000 372033439 234000 240000 246000 25200...

output:

41604524046237
-69493320543288
6338462812847
1460065516810
-7637138571620
23156372007655
-1370724064791
28390231212091
40937971916975
56065631201796
94048155272925
32230016028635
65423756137695
37887327902181
85369989782338
42561657079062
-8608926849694
7255189107425
24025628399697
58546594191277
84...

result:

wrong answer 1st numbers differ - expected: '41604941994237', found: '41604524046237'

Test #4:

score: 0
Wrong Answer
time: 16ms
memory: 54392kb

input:

300000 600000
-370584886 -824446876 -217953152 -213883201 -3695086 -244661761 -31643401 -28513584 -120242422 -164834515 -442171367 -44150185 -373313047 -176037889 -88006209 13397 -137034887 -288429275 -105994131 9344897 -561275521 -739928113 -410398492 -766560640 -234474561 -376898910 -3876489 -7672...

output:

result:

wrong answer Answer contains longer sequence [length = 299107], but output contains 0 elements

Test #5:

score: 0
Wrong Answer
time: 35ms
memory: 53116kb

input:

300000 600000
211880591 88968133 407526653 911890111 807256887 -176021101 106280356 8936401 282861019 5357877 254177 417572162 -357964741 -381515641 129902155 473664349 -59617567 667379417 776235315 58916209 7886485 223802672 -47045571 804252695 203831125 43372991 28892923 158908981 378392554 -30512...

output:

11754434464462
-44496111272162
20568120946771
-28201773606268
10748476963658
24048083672408
18461993014687
8655617113084
34394177405859
-40060770418859
-49247813090767
0
-49084378853052
-72322234878633
72959358358759
-4439116870003
-25487478941630
6939736078217
-47902205973503
33450295618240
2449803...

result:

wrong answer 1st numbers differ - expected: '4942713365399', found: '11754434464462'

Test #6:

score: 0
Wrong Answer
time: 30ms
memory: 53120kb

input:

300000 600000
478547749 21607029 -89838541 489455731 -26326441 -57796177 11291418 580134112 194452929 323639427 78318073 26812402 543586369 370325145 -15025771 77970751 -57165081 69553200 68373559 103525821 488338363 -114852353 129257857 353303549 120029521 55251574 184069369 116347321 66298177 2323...

output:

0
-14298986184412
1286541581357
-2043418198457
39623452073354
-16501499994831
21498803673884
51480341221044
-65870708369351
-22480172651981
0
-39115750181877
53991718383468
-1448370764570
53849791462274
-9418913376755
-4890632530435
-4827948711904
-3437806262300
-52618231772242
5133860620166
-627848...

result:

wrong answer 1st numbers differ - expected: '2236198842134', found: '0'

Test #7:

score: 0
Wrong Answer
time: 27ms
memory: 53020kb

input:

300000 600000
-167628 147836 342193 -113005 335767 62551 37153 391126 62081 394393 64376 61561 204691 362478 -192721 246628 -34842 558316 210421 492772 63566 -119326 208751 549977 400921 424726 242537 401281 -156335 392551 175009 213401 277477 510111 27205 90706 544489 166673 325195 362819 -1502 497...

output:

25746849671820
-36691932937061
0
-16247428336869
9878907606061
3532007306591
22090190513819
-17347021274402
-40839935582432
-882449847030
0
748030804487
21651693032387
-39464132159638
-35570929666984
4230730369218
29957181072202
-38613871514787
-9309207829312
-18033868368088
32712839548702
-12313390...

result:

wrong answer 1st numbers differ - expected: '26438246588', found: '25746849671820'

Test #8:

score: 0
Wrong Answer
time: 23ms
memory: 52844kb

input:

300000 600000
-52710799 -139860657 -76037377 -383460841 -250485933 -170800931 38569417 -148104385 -366126471 36758571 61991329 -179464171 -336298825 -58594900 22133163 -423137793 -364236327 37740025 -191822446 -86831549 68026423 -113477261 -80044118 -45362365 -154807957 -29767662 -474689591 -1954812...

output:

result:

wrong answer Answer contains longer sequence [length = 119802], but output contains 0 elements

Test #9:

score: 0
Wrong Answer
time: 16ms
memory: 52824kb

input:

300000 600000
-9317 -17721 83807 -89601 -132992 -21217 -164947 -15601 -168899 190720 -33799 -114351 -91457 -194029 132053 -109571 -65991 -107846 -77121 -90550 -162626 -66021 -52064 -69881 55395 -187207 -41697 -152345 76528 -97151 -172721 100673 -190401 -29409 -62929 -112268 -92705 -165993 -61056 -37...

output:

result:

wrong answer Answer contains longer sequence [length = 479590], but output contains 0 elements

Test #10:

score: 0
Wrong Answer
time: 21ms
memory: 52916kb

input:

300000 600000
-9317 -17721 83807 -89601 -132992 -21217 -164947 -15601 -168899 190720 -33799 -114351 -91457 -194029 132053 -109571 -65991 -107846 -77121 -90550 -162626 -66021 -52064 -69881 55395 -187207 -41697 -152345 76528 -97151 -172721 100673 -190401 -29409 -62929 -112268 -92705 -165993 -61056 -37...

output:

result:

wrong answer Answer contains longer sequence [length = 479590], but output contains 0 elements

Test #11:

score: 0
Wrong Answer
time: 12ms
memory: 54740kb

input:

300000 600000
-350031 -418621 -379153 -349541 -204935 -413677 -290785 -73634 -339579 -86194 -237211 -393502 -477091 -479966 -452057 -384481 -843294 -221408 -132345 -109333 -149097 -483897 -29033 -220275 -50099 -39225 -148729 -397731 -222829 -436818 -233585 -433945 -335641 -44285 -107328 -338151 -534...

output:

result:

wrong answer Answer contains longer sequence [length = 360608], but output contains 0 elements

Test #12:

score: 0
Wrong Answer
time: 18ms
memory: 52900kb

input:

300000 600000
-696987827 1791548840 1540245114 -744556712 281332436 -396365348 -660700017 -926408705 66098449 1448486061 -1945919603 1080362360 732219815 -519568302 1228792006 364734706 -1151351486 -1056003603 -1852483513 -1758573146 762059937 -333873273 -1645890512 1388909837 -267565502 1028489524 ...

output:

result:

wrong answer Answer contains longer sequence [length = 301015], but output contains 0 elements
English 繁體中文 简体中文

Server Time: 2024-12-03 21:10:44 | OpenSource Project