QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225790 | #5403. 树数术 | chenxinyang2006 | 100 ✓ | 1892ms | 410708kb | C++14 | 5.2kb | 2023-10-25 09:04:10 | 2023-10-25 09:04:10 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n,m,q;
int a[700005],b[700005];
int cnt;
int head[700005];
struct eg{
int to,nxt;
}edge[1400005];
void make(int u,int v){
edge[++cnt].to = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
int dfn[700005],siz[700005],fa[700005],dep[700005];
int ST[21][700005];
void dfs(int u,int f){
dfn[u] = ++cnt;
ST[0][cnt] = u;
fa[u] = f;
dep[u] = dep[f] + 1;
siz[u] = 1;
for(int i = head[u];i;i = edge[i].nxt){
int v = edge[i].to;
if(v == f) continue;
dfs(v,u);
siz[u] += siz[v];
}
}
inline int cmp(int x,int y){
if(dep[x] < dep[y]) return x;
return y;
}
inline int query(int l,int r){
int x = __lg(r - l + 1);
return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}
inline int LCA(int u,int v){
if(u == v) return u;
u = dfn[u];v = dfn[v];
if(u > v) swap(u,v);
return fa[query(u + 1,v)];
}
struct fenwick{
int tree[700005];
#define lowbit(x) (x & (-x))
void upd(int pos,int C){
while(pos <= n){
chkmax(tree[pos],C);
pos += lowbit(pos);
}
}
int qry(int pos){
int res = 0;
while(pos){
chkmax(res,tree[pos]);
pos -= lowbit(pos);
}
return res;
}
}Ord,Rev;
struct rangelca{
int ST[21][700005],op;//op=0 最小值.op=1 最大值
inline int cmp(int x,int y){
if(!op){
if(dfn[x] < dfn[y]) return x;
return y;
}
if(dfn[x] > dfn[y]) return x;
return y;
}
void init(){
rep(i,1,m) ST[0][i] = a[i];
rep(i,1,19){
rep(j,1,m){
if(j + (1 << i) - 1 > m) break;
ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]);
}
}
}
inline int qry(int l,int r){
int x = __lg(r - l + 1);
return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}
}Mn,Mx;
inline int getres(int l,int r){
return LCA(Mn.qry(l,r),Mx.qry(l,r));
}
int sz,_sz;
ll result[700005];
struct qry{
int x,y,id,op;
}Q[2800005],sp[2100005],tmp[2800005];
bool cmp2(qry s,qry t){
if(s.x != t.x) return s.x < t.x;
return s.id < t.id;
}
vector <qry> QQ[700005];
vector <int> PP[700005];
void dfs2(int u){
for(int id:PP[u]) Q[++sz] = {id,b[id],0,1};
for(qry I:QQ[u]){
Q[++sz] = {I.y,I.x,I.id,1};
Q[++sz] = {I.x - 1,I.x,I.id,-1};
}
for(int i = head[u];i;i = edge[i].nxt){
int v = edge[i].to;
if(v == fa[u]) continue;
dfs2(v);
}
for(int id:PP[u]) Q[++sz] = {id,b[id],0,-1};
}
int tree[700005];
#define lowbit(x) (x & (-x))
void upd(int pos,int C){
while(pos <= m){
tree[pos] += C;
pos += lowbit(pos);
}
}
int query(int pos){
int res = 0;
while(pos){
res += tree[pos];
pos -= lowbit(pos);
}
return res;
}
void cdq(int l,int r){
if(l == r) return;
int mid = (l + r) >> 1;
cdq(l,mid);cdq(mid+1,r);
int j = l;
rep(i,mid+1,r){
while(j <= mid && Q[j].x <= Q[i].x){
if(!Q[j].id) upd(Q[j].y,Q[j].op);
j++;
}
if(Q[i].id) result[Q[i].id] += Q[i].op * query(Q[i].y);
}
while(j > l){
j--;
if(!Q[j].id) upd(Q[j].y,-Q[j].op);
}
int i = l,k = l;
j = mid + 1;
while(i <= mid && j <= r){
if(Q[i].x < Q[j].x) tmp[k++] = Q[i++];
else tmp[k++] = Q[j++];
}
while(i <= mid) tmp[k++] = Q[i++];
while(j <= r) tmp[k++] = Q[j++];
for(i = l;i <= r;i++) Q[i] = tmp[i];
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d%d%d",&n,&m,&q);
rep(i,1,n - 1){
int u,v;
scanf("%d%d",&u,&v);
make(u,v);make(v,u);
}
cnt = 0;
dfs(1,0);
rep(i,1,19){
rep(j,1,n){
if(j + (1 << i) - 1 > n) break;
ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]);
}
}
rep(i,1,m){
scanf("%d",&a[i]);
PP[a[i]].eb(i);
int u = a[i];
b[i] = max(Ord.qry(dfn[u] - 1),Rev.qry(n - dfn[u] - siz[u] + 1)) + 1;
Ord.upd(dfn[u],i);
Rev.upd(n - dfn[u] + 1,i);
}
// rep(i,1,m) printf("%d ",b[i]);
// printf("\n");
Mn.op = 0;Mx.op = 1;
Mn.init();Mx.init();
int k,l,r,u;
rep(i,1,q){
scanf("%d",&k);
rep(j,1,k){
scanf("%d%d",&l,&r);
if(j == 1){
sp[++_sz] = {r,l,i,1};
sp[++_sz] = {l - 1,l,i,-1};
u = getres(l,r);
}else{
QQ[u].push_back({l,r,i,0});
u = LCA(u,getres(l,r));
}
}
}
rep(i,1,m) sp[++_sz] = {i,b[i],0,1};
dfs2(1);
// rep(i,1,sz) printf("%d %d %d %d\n",Q[i].x,Q[i].y,Q[i].id,Q[i].op);
cdq(1,sz);
sort(sp + 1,sp + _sz + 1,cmp2);
rep(i,1,_sz){
if(!sp[i].id) upd(sp[i].y,sp[i].op);
else result[sp[i].id] += sp[i].op * query(sp[i].y);
}
rep(i,1,q) printf("%lld\n",result[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1892ms
memory: 410708kb
input:
699990 699995 233333 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
121987 139520 87432 42773 311773 194269 177810 454211 417130 299450 366103 227736 186417 163975 292497 216139 401719 16634 192685 27351 52127 54938 142169 275076 339876 117003 51132 229206 187647 350043 398455 83905 100490 338070 356664 60211 366172 142627 16903 222331 471095 184145 170758 238393 14...
result:
ok 233333 lines
Subtask #2:
score: 20
Accepted
Test #2:
score: 20
Accepted
time: 1309ms
memory: 359308kb
input:
699992 699994 699992 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 40 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
211594 160846 176729 128251 32662 70710 74884 9095 68282 91324 154262 24279 31878 173468 75265 139715 91660 87525 194302 16875 81535 172911 29145 20483 151883 5255 9548 58890 38076 94152 14358 74859 48870 23981 41390 60976 13795 125823 427 26641 130620 174231 73241 55291 2364 78864 23391 4866 36002 ...
result:
ok 699992 lines
Subtask #3:
score: 30
Accepted
Test #3:
score: 30
Accepted
time: 183ms
memory: 196976kb
input:
99998 99993 33333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 24 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 49 ...
output:
9733 11330 8403 5136 22207 23231 12686 27288 23739 20937 18153 16379 8991 14036 11669 14685 20272 18955 21680 7927 21383 23576 14834 5714 15707 10013 7905 13254 13883 10446 16140 16796 11009 11912 15761 20419 11157 12192 14327 18260 19095 5239 4114 16522 7412 5005 16844 8747 19377 22600 12023 9161 9...
result:
ok 33333 lines
Subtask #4:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #4:
score: 40
Accepted
time: 1834ms
memory: 378116kb
input:
699991 700000 233333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
129494 81962 52243 146978 53574 96058 72866 34286 184144 65111 77323 90610 168465 55995 66592 60741 118767 119126 150909 50321 114540 119576 122486 84546 19256 4585 22720 133448 124662 148500 173817 100034 135869 88299 68523 62880 73171 139874 90190 100601 100854 137709 106869 126901 40873 93249 136...
result:
ok 233333 lines