ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#204048 | #564. 多重集合问题 | snow_trace | 100 | 10058ms | 340132kb | C++11 | 3.1kb | 2024-04-06 10:10:19 | 2024-04-06 12:11:24 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dep[200005],lca[200005][19],dfn[200005],ssz[200005];
vector<int>p[200005];
int trie[40000005][2];long long sz[40000005];int nw = 0;
struct node{
int l,r,rt;
}tree[800005];
inline void ins(int now,int x,int k){
sz[now]+=k;
for(int i = 29;i>=0;i--){
bool a = x>>i&1;
if(!trie[now][a])trie[now][a] = ++nw;
now = trie[now][a];sz[now]+=k;
}
}inline long long query(int now,int a,int b){
long long ans = 0;
//cout << " " << now << " " << a << " " << b << endl;
for(int i = 29;i>=0;i--){if(!now)break;
bool aa = a>>i&1,bb = b>>i&1;
// cout << " " << aa << " " << bb << endl;
if(bb == 0){
now = trie[now][aa];
}else{
// cout << " " << trie[now][a] << " " << sz[trie[now][aa]] << endl;
ans+=sz[trie[now][aa]];now = trie[now][1^aa];
}
}return ans+sz[now];
//x^a<b
}
void build(int l,int r,int k){
tree[k].l = l,tree[k].r = r;
tree[k].rt = ++nw;
if(l+1 == r){
return;
}build(l,l+r>>1,k<<1),build(l+r>>1,r,k<<1|1);
}void update(int l,int r,int x,int nn,int k){
int ll = tree[k].l,rr = tree[k].r;
if(ll>=r or l>=rr)return;
if(l<=ll and rr<=r){
ins(tree[k].rt,x,nn);return;
}update(l,r,x,nn,k<<1),update(l,r,x,nn,k<<1|1);
}long long qquery(int pos,int k,int a,int b){
int l = tree[k].l,r = tree[k].r;
long long rr = query(tree[k].rt,a,b);
if(l+1 == r)return rr;
int mid =l +r>>1;
if(pos<mid)return qquery(pos,k<<1,a,b)+rr;
return qquery(pos,k<<1|1,a,b)+rr;
}
int cc;
void dfs(int now,int fa){
ssz[now] = 1,dep[now] = dep[fa]+1,dfn[now] = ++cc;
lca[now][0] = fa;for(int i = 1;i<=18;i++)lca[now][i] = lca[lca[now][i-1]][i-1];
for(int i= 0;i<p[now].size();i++){
if(p[now][i] == fa)continue;
dfs(p[now][i],now);ssz[now]+=ssz[p[now][i]];
}
}int kth(int x,int k){
for(int i =0;k;k>>=1,i++)if(k&1)x = lca[x][i];return x;
}
int lcaa(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int dis = dep[x]-dep[y];
for(int i =0;dis;dis>>=1,i++)if(dis&1)x = lca[x][i];
if(x == y)return x;
for(int i = 18;i>=0;i--){
if(lca[x][i]!=lca[y][i]){
x = lca[x][i],y = lca[y][i];
}
}return lca[x][0];
}int nrt = 1;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1;i<n;i++){
int a,b;cin >> a >> b;
p[a].push_back(b),p[b].push_back(a);
}dfs(1,1);build(1,n+1,1);
int q;cin >> q;
while(q--){
int op;cin >> op;
if(op == 1){
//假如在根和1之间需要特判
int v,x,k;cin >> v >> x >> k;
if(lcaa(nrt,v) == v){
update(1,n+1,x,k,1);
if(v == nrt){
continue;
}
int nxt = kth(nrt,abs(dep[nrt]-dep[v])-1);
update(dfn[nxt],dfn[nxt]+ssz[nxt],x,-k,1);
}else{
update(dfn[v],dfn[v]+ssz[v],x,k,1);
}
}if(op == 2){
int v,a,b;cin >> v >> a >> b;
long long ans = qquery(dfn[v],1,a,b);
cout << ans << '\n';
}if(op == 3){
cin >> nrt;
}
}
return 0;
}/*
这么大的 DS 题你不给我大洋里我写牛魔呢 /wx/wx/wx
线段树套 trie,换根很套路。
4
1 2
1 3
3 4
14
1 1 1 1
1 2 2 1
1 3 3 1
2 1 0 4
2 2 1 3
2 4 3 2
3 4
1 3 3 1
1 4 4 1
1 1 1 1
1 2 2 1
2 1 0 4
2 2 1 3
2 4 3 2
1
2
1 1 3 2
2 1 1 2
*/
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 6ms
memory: 6488kb
input:
500 244 90 412 244 93 412 488 90 79 93 340 412 207 340 408 93 452 79 200 79 182 408 424 79 157 182 8...
output:
0 0 0 0 0 0 566198873 88418523 0 447687853 417410646 88418523 1138954231 252822794 0 0 88418523 0 0 ...
result:
ok 58 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 6772kb
input:
500 183 146 183 144 183 397 397 32 32 95 144 233 233 254 397 247 95 309 247 81 254 24 24 424 24 482 ...
output:
0 356895596 0 653090121 1260518543 0 2187569813 1536809911 653090121 4346333812 2934191048 280676296...
result:
ok 51 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 6172kb
input:
2 2 1 500 1 2 341404994 582616173 1 1 37451687 382659157 1 2 386934479 438560511 1 2 61268050 701143...
output:
2599988434 7706270673 17290581682 33614581607 34031096649 2608282159 10908180780 30251498013 1290000...
result:
ok 52 tokens
Test #4:
score: 0
Accepted
time: 0ms
memory: 6360kb
input:
13 12 3 3 11 12 4 11 9 11 2 9 10 9 6 4 7 2 1 7 13 6 8 6 5 500 1 3 325914127 283078917 1 13 627147976...
output:
2218191976 0 3542581422 3375269022 10620630750 6476407121 3243274252 6791312373 5510518139 188883967...
result:
ok 53 tokens
Test #5:
score: 0
Accepted
time: 3ms
memory: 6448kb
input:
500 45 290 147 290 88 45 226 45 313 290 423 88 344 423 288 45 46 226 107 313 108 313 330 290 73 344 ...
output:
0 0 1311260699 1036424713 1036424713 1036424713 0 30392645 0 0 0 1418025799 1845009357 0 0 0 1036424...
result:
ok 46 tokens
Test #6:
score: 0
Accepted
time: 7ms
memory: 6728kb
input:
500 459 9 9 42 42 385 42 392 459 402 385 292 385 55 385 299 402 31 55 481 481 490 481 61 299 412 481...
output:
0 0 0 0 0 0 0 0 0 514099530 1315138132 0 1328932960 0 3703627416 795669584 5678344966 0 4154749998 2...
result:
ok 51 tokens
Test #7:
score: 0
Accepted
time: 0ms
memory: 6456kb
input:
280 249 69 83 249 34 249 210 34 32 249 136 210 159 249 246 136 166 249 176 246 121 159 230 69 108 34...
output:
0 687887638 0 707352338 588720084 19464700 687887638 19464700 1103264581 687887638 1469726377 191502...
result:
ok 45 tokens
Test #8:
score: 0
Accepted
time: 0ms
memory: 6236kb
input:
430 325 30 325 41 41 185 325 404 185 417 404 299 404 348 299 407 348 84 299 378 407 152 84 339 407 3...
output:
0 0 698742390 0 252808268 0 0 0 2568472240 1490064534 1891821796 303962175 5860090068
result:
ok 13 tokens
Subtask #2:
score: 14
Accepted
Test #9:
score: 14
Accepted
time: 82ms
memory: 33368kb
input:
1 140000 2 1 576147149 772634763 1 1 396417010 92525865 1 1 991921618 1031225962 1 1 235592921 15079...
output:
0 10548880744 0 11035968403 0 434945668 4199008278 8554196900 11643712050 3509407981 16617382327 239...
result:
ok 13710 tokens
Test #10:
score: 0
Accepted
time: 159ms
memory: 33368kb
input:
1 140000 1 1 601243317 310785008 1 1 756350798 1070171392 1 1 809165721 925680784 1 1 62107755 55493...
output:
554935117 4586081606 11118112083 6054293998 5161117439 17530754643 25064513721 11410247010 407575270...
result:
ok 13742 tokens
Test #11:
score: 0
Accepted
time: 130ms
memory: 33380kb
input:
1 140000 2 1 85280416 820771523 1 1 1056295621 95349983 1 1 298938814 121898587 1 1 812343482 891760...
output:
0 3319311386 1397429405 0 13337569619 15666488362 5075202465 35432684863 42810838259 8230761582 3229...
result:
ok 13693 tokens
Test #12:
score: 0
Accepted
time: 74ms
memory: 33332kb
input:
1 140000 2 1 110343816 358921768 1 1 342487585 1072995510 1 1 116150149 16353409 1 1 638858316 22222...
output:
0 3046925655 818858034 18912173493 7628605816 3499749266 37357017239 3469268217 18016540602 35799368...
result:
ok 13899 tokens
Test #13:
score: 0
Accepted
time: 86ms
memory: 33356kb
input:
1 140000 1 1 135439984 970879372 1 1 702388605 976931981 1 1 1007070539 984550055 1 1 465373150 6263...
output:
0 15944697871 12194262560 4997618152 39398394529 40904079530 52545013433 63929272194 1434989091 4667...
result:
ok 13736 tokens
Test #14:
score: 0
Accepted
time: 67ms
memory: 33332kb
input:
1 140000 1 1 160503383 509062384 2 1 1062355161 880868453 1 1 824281873 879037645 1 1 291920753 1030...
output:
0 4475900441 4936679861 3195031318 16470492089 30164302445 39447055252 1341353668 34501618323 475292...
result:
ok 13953 tokens
Subtask #3:
score: 15
Accepted
Test #15:
score: 15
Accepted
time: 141ms
memory: 87772kb
input:
50000 23353 32918 23165 32918 42334 23165 37266 32918 36241 37266 48241 36241 30134 42334 5022 42334...
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 ...
result:
ok 9729 tokens
Test #16:
score: 0
Accepted
time: 445ms
memory: 230140kb
input:
10000 8523 2979 8523 5212 8523 8063 5212 9095 9095 754 754 2186 9095 534 9095 8973 2186 1722 754 539...
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 ...
result:
ok 13723 tokens
Test #17:
score: 0
Accepted
time: 141ms
memory: 62660kb
input:
140000 18963 105564 30407 18963 62244 18963 77218 105564 5670 18963 137321 62244 91120 62244 111337 ...
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 ...
result:
ok 3902 tokens
Test #18:
score: 0
Accepted
time: 234ms
memory: 126876kb
input:
140000 110867 63174 63174 25637 63174 71796 63174 73409 73409 76383 25637 36626 36626 90597 76383 90...
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 ...
result:
ok 3880 tokens
Test #19:
score: 0
Accepted
time: 455ms
memory: 134292kb
input:
140000 124760 17961 11053 124760 128007 124760 109257 124760 95880 128007 33568 128007 91823 11053 1...
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 ...
result:
ok 13716 tokens
Test #20:
score: 0
Accepted
time: 851ms
memory: 335872kb
input:
140000 132301 113503 132301 8970 132301 71982 8970 38942 8970 75118 113503 37832 37832 111571 75118 ...
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 ...
result:
ok 13686 tokens
Test #21:
score: 0
Accepted
time: 359ms
memory: 134764kb
input:
140000 9009 132135 103722 132135 66217 132135 138028 66217 132757 138028 3788 132757 139979 3788 450...
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 ...
result:
ok 13767 tokens
Test #22:
score: 0
Accepted
time: 816ms
memory: 333688kb
input:
140000 74249 108669 74249 126812 74249 71764 74249 78093 71764 129403 71764 121546 129403 87766 8776...
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 ...
result:
ok 13813 tokens
Subtask #4:
score: 23
Accepted
Test #23:
score: 23
Accepted
time: 142ms
memory: 52876kb
input:
50000 46569 8980 39271 8980 39589 46569 5017 39589 23140 5017 2759 8980 33776 46569 1593 33776 1461 ...
output:
0 0 0 0 0 0 0 39902982 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 4994 tokens
Test #24:
score: 0
Accepted
time: 254ms
memory: 118016kb
input:
50000 22404 4201 4201 46667 46667 34698 46667 39944 39944 40878 46667 20211 20211 35478 39944 17680 ...
output:
933652152 0 2375845635 0 709713347 687670164 1355345803 3608644834 4952561203 709713347 8086571005 0...
result:
ok 5026 tokens
Test #25:
score: 0
Accepted
time: 143ms
memory: 52548kb
input:
50000 9822 28016 13645 9822 46865 13645 26017 46865 7350 46865 28109 26017 25795 46865 8982 7350 349...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 461880698 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 4994 tokens
Test #26:
score: 0
Accepted
time: 253ms
memory: 117608kb
input:
49999 22725 15994 15994 20311 15994 31578 20311 32700 20311 28270 32700 13245 20311 42919 42919 1559...
output:
499309076 499309076 529723643 2712007057 963524930 1270035832 1799759475 9812205988 0 7177810666 191...
result:
ok 4994 tokens
Test #27:
score: 0
Accepted
time: 77ms
memory: 51976kb
input:
50000 23427 7956 48134 7956 39627 7956 42939 23427 1263 42939 43960 7956 39891 42939 19124 42939 947...
output:
0 0 0 0 0 0 0 0 782916692 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 399414566 0 0 0 0 0 0 0 0 166482893 0 0 ...
result:
ok 4939 tokens
Test #28:
score: 0
Accepted
time: 182ms
memory: 119328kb
input:
50000 29693 37097 29693 26099 29693 26661 37097 25535 26099 9909 37097 20408 26661 26364 9909 966 96...
output:
0 0 0 0 0 0 0 0 6097940120 1651113081 0 205287252 3892118560 7479546034 10442712552 2895904154 0 489...
result:
ok 5028 tokens
Subtask #5:
score: 21
Accepted
Test #29:
score: 21
Accepted
time: 80ms
memory: 52080kb
input:
50000 39387 7957 11949 39387 34768 39387 33546 34768 44523 34768 41098 7957 28433 7957 17150 7957 41...
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 1066342039 0 0 0 0 0 0 0 0 0...
result:
ok 4933 tokens
Test #30:
score: 0
Accepted
time: 163ms
memory: 115720kb
input:
49999 35918 22868 35918 7032 7032 36310 36310 12621 35918 49336 12621 41846 36310 18905 41846 13438 ...
output:
677603658 677603658 1117450312 1666088414 0 3144959829 2328932306 1002358032 580923286 1925681320 64...
result:
ok 4900 tokens
Test #31:
score: 0
Accepted
time: 61ms
memory: 40720kb
input:
3000 2954 2434 2906 2434 2953 2954 2930 2953 2995 2953 2218 2930 801 2906 1659 2218 198 2906 1326 29...
output:
0 0 0 0 0 0 0 0 0 0 0 940816787 0 0 0 0 0 1023141047 1023141047 255064797 1963957834 1023141047 1023...
result:
ok 4910 tokens
Test #32:
score: 0
Accepted
time: 105ms
memory: 73520kb
input:
2000 1752 357 357 1591 1752 976 976 1803 1591 1429 357 1198 1198 576 576 17 1803 600 1198 1760 1760 ...
output:
0 0 0 648766211 0 421680852 0 149392927 149392927 0 0 3047694144 0 793131974 3770638680 0 4168551832...
result:
ok 4958 tokens
Test #33:
score: 0
Accepted
time: 94ms
memory: 51828kb
input:
50000 2764 5807 45488 5807 7579 2764 28703 5807 10247 2764 5171 7579 19758 5171 16625 5807 44789 757...
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 27365038...
result:
ok 4908 tokens
Test #34:
score: 0
Accepted
time: 250ms
memory: 116884kb
input:
50000 45220 36892 45220 20170 36892 17195 36892 31634 45220 40807 17195 38628 31634 19791 40807 3845...
output:
820550535 1118416783 0 1648529134 5967460758 2579160544 2011855989 4620324005 3645630996 3768063157 ...
result:
ok 4875 tokens
Test #35:
score: 0
Accepted
time: 143ms
memory: 52112kb
input:
50000 45373 26713 15979 45373 25083 15979 23188 26713 21084 45373 1522 26713 26101 23188 42393 26713...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 599092872 0 0 0 0 0 0 0 0 0 0 599092872 0 0 0 0 0 0 0 0 0 0 0 7118...
result:
ok 4947 tokens
Test #36:
score: 0
Accepted
time: 312ms
memory: 116552kb
input:
50000 44176 34155 34155 11131 44176 15704 15704 23727 44176 47929 11131 35503 47929 9193 9193 16258 ...
output:
482423793 0 0 0 0 913806153 736125415 0 1593504425 6764621961 1600443187 3958600150 0 3025771517 608...
result:
ok 4950 tokens
Subtask #6:
score: 20
Accepted
Test #37:
score: 20
Accepted
time: 398ms
memory: 134836kb
input:
140000 63337 114625 26384 114625 32063 114625 75167 63337 84354 32063 55609 84354 2313 84354 75757 6...
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 ...
result:
ok 13774 tokens
Test #38:
score: 0
Accepted
time: 751ms
memory: 338852kb
input:
140000 27336 30368 30368 69843 30368 37026 37026 77396 30368 70989 69843 36739 77396 49374 49374 798...
output:
0 895826918 0 1221105604 162695280 2579993948 4343869477 987883548 4463791047 0 895826918 2429682906...
result:
ok 13757 tokens
Test #39:
score: 0
Accepted
time: 264ms
memory: 127048kb
input:
100000 59233 74815 85046 59233 57158 59233 83574 59233 99894 57158 64405 99894 12177 64405 76952 121...
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 ...
result:
ok 13562 tokens
Test #40:
score: 0
Accepted
time: 813ms
memory: 331328kb
input:
140000 86512 71025 71025 58046 86512 137372 71025 49097 137372 133566 71025 136193 137372 27441 4909...
output:
0 0 0 0 971699863 5482565746 0 890462365 8063678010 1937213907 0 3145762434 11982563520 10081700216 ...
result:
ok 13590 tokens
Test #41:
score: 0
Accepted
time: 481ms
memory: 134748kb
input:
140000 116172 95295 95107 95295 96592 116172 126232 96592 11299 95107 88780 95107 125782 11299 18949...
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 ...
result:
ok 13597 tokens
Test #42:
score: 0
Accepted
time: 1036ms
memory: 340132kb
input:
140000 7209 64363 7209 43346 7209 9374 7209 67917 9374 3348 43346 73336 43346 85263 67917 123357 733...
output:
0 0 0 851958002 2151784985 1200990938 1056563582 2110067245 0 4521410217 6716703670 0 4593108547 407...
result:
ok 13609 tokens