QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#420815#5403. 树数术Crying0 0ms0kbC++143.5kb2024-05-24 22:22:562024-05-24 22:22:57

Judging History

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

  • [2024-05-24 22:22:57]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-05-24 22:22:56]
  • 提交

answer

#include<bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;
typedef long long ll;
typedef array<int,2> pr; typedef array<int,3> tr;
const int MAXN = 7e5+10,INF = 1e9;
void tomin(int& x,int y){x = min(x,y);}
void tomax(int& x,int y){x = max(x,y);}
//
int n,m,q,k,a[MAXN]; ll ans[MAXN];
int L[MAXN],R[MAXN],f[MAXN];
vector<int> e[MAXN];

struct ST{
    int st[21][MAXN*2]; int key[MAXN*2],id[MAXN*2];
    int cmp(int x,int y){return key[x] < key[y] ? x : y;}
    void build(int n,int* a,int* b){
        for(int i=1;i<=n;i++)key[i] = a[i],id[i] = b[i],st[0][i] = i;
        for(int j=1;j<=20;j++)for(int i=1;i<=n-(1<<j)+1;i++)st[j][i] = cmp(st[j-1][i],st[j-1][i+(1<<(j-1))]);
    }
    int qry(int l,int r){
        int len = __lg(r-l+1);
        return id[cmp(st[len][l],st[len][r-(1<<len)+1])];
    }
};

namespace _{  //lca
    int dfn[MAXN*2],ord[MAXN],dep[MAXN],dtot;
    int a[MAXN*2],b[MAXN*2]; ST st;
    void dfs(int u,int fa){
        dfn[++dtot] = u,ord[u] = dtot;
        for(auto v : e[u])if(v != fa){
            dep[v] = dep[u]+1;
            dfs(v,u);
            dfn[++dtot] = u;
        }
    }
    void solve(){
        dfs(1,0);
        for(int i=1;i<=dtot;i++)a[i] = dep[dfn[i]],b[i] = dfn[i];
        st.build(dtot,a,b);
    }
    int lca(int x,int y){
        x = ord[x],y = ord[y]; if(x>y)swap(x,y);
        return st.qry(x,y);
    }
}; using _::lca;

int dfn[MAXN],sz[MAXN],dtot; int b[MAXN*2],c[MAXN*2]; ST st;
void dfs(int u,int fa){
    dfn[u] = ++dtot; sz[u] = 1;
    for(auto v : e[u])if(v != fa){
        dfs(v,u); sz[u] += sz[v];
    }
}
int chk(int x,int y){return dfn[x] <= dfn[y] && dfn[x]+sz[x] > dfn[y];}
int qry(int l,int r){
    assert(l<=r);
    int x = st.qry(l,r),y = st.qry(l+m,r+m);
    return lca(x,y);
}

struct BIT{
    int t[MAXN];
    void mdf(int x){ for(;x<=m;x+=lowbit(x))t[x]++;}
    int qry(int x,int S=0){for(;x;x-=lowbit(x))S += t[x];return S;}
}bit;
vector<tr> o[MAXN];

int main(){
    freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);

    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m>>q;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        e[u].push_back(v); e[v].push_back(u);
    }
    _::solve();
    for(int i=1;i<=m;i++)cin>>a[i]; 
    dfs(1,0);
    for(int i=1;i<=m;i++)b[i] = dfn[a[i]],b[i+m] = -dfn[a[i]],c[i] = c[i+m] = a[i];
    st.build(2*m,b,c);
    for(int i=1;i<=m;i++){
        int L = 1,R = i-1; f[i] = i;
        while(L<=R){
            int mid = (L+R)>>1;
            if(chk(a[i],qry(mid,i)))f[i] = mid,R = mid-1;
            else L = mid+1;
        }
    }
    //

    for(int id=1;id<=q;id++){
        cin>>k;
        for(int i=1;i<=k;i++)cin>>L[i]>>R[i];
        auto opt = [&](int l,int r,int lim){
            if(l>r)return;
            o[r].push_back({lim,1,id});
            o[l-1].push_back({lim,-1,id});
        };     
        opt(L[1],R[1],L[1]); int p = qry(L[1],R[1]);
        for(int i=2;i<=k;i++){
            int l = L[i],r = R[i],ret = R[i]+1;
            while(l<=r){
                int mid = (l+r)>>1;
                int q = qry(L[i],mid);
                if(chk(q,p))ret = mid,r = mid-1;
                else l = mid+1;
            }
            opt(ret,R[i],L[i]);
            p = lca(p,qry(L[i],R[i]));
        }
    }

    //
    for(int i=1;i<=m;i++){
        bit.mdf(f[i]);
        for(auto [lim,v,id] : o[i]){
            ans[id] += v * bit.qry(lim);
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

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:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #2:

score: 0
Dangerous Syscalls

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:


result:


Subtask #3:

score: 0
Dangerous Syscalls

Test #3:

score: 0
Dangerous Syscalls

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:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%