2022国庆acm刷题训练

训练 知乎
ICPC
发布日期:   2022-09-30
更新日期:   2022-10-09
文章字数:   5.4k
阅读时长:   31 分
阅读次数:   11

[TOC]

预期题单

9月30号

Codeforces Beta Round #19 D

数组离散化unique的时候是伪删除会把重复元素放到数组后面
这道题采取树套树的思想，线段树套一个set

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
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
#define ls u<<1
#define rs u<<1|1
typedef pair<int,int>PII;
int T,x,y,cnt,a[N],b[N],s[N*4];
string op;
set<int>S[N*4];
struct Query{
    string op;
    int x,y;
}Q[N];
void pushup(int u){s[u]=max(s[ls],s[rs]);}
int len;
void modify(int u,int x,int y,int op=1,int l=0,int r=len){
    if(l==r){
        if(op==1)S[u].insert(y);
        else S[u].erase(y);
        if(S[u].size()==0)s[u]=0;
        else s[u]=*(--S[u].end());
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls,x,y,op,l,mid);
    else modify(rs,x,y,op,mid+1,r);
    pushup(u);
}
auto p=make_pair(-1,-1);
PII q(int u,int x,int y,int l=0,int r=len){
    if(r<x)return p;
    if(s[u]<y)return p;
    if(l==r)return make_pair(l,*S[u].lower_bound(y));
    int mid=l+r>>1;
    auto L=q(ls,x,y,l,mid);
    if(L==p)return q(rs,x,y,mid+1,r);
    else return L;
}
int mp[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    for(int i=1;i<=T;i++){
        cin>>op>>x>>y;
        Q[i]={op,x,y};
        a[cnt++]=x,a[cnt++]=y;
    }
    sort(a,a+cnt);
    len=unique(a,a+cnt)-a;
    for(int i=1;i<=T;i++){
        op=Q[i].op,x=Q[i].x,y=Q[i].y;
        int k=1;
        if(op=="remove")k=-1;
        if(op=="find"){
            x=lower_bound(a,a+len,x+1)-a;
            y=lower_bound(a,a+len,y+1)-a;
            auto t=q(1,x,y);
            if(t==p)cout<<-1<<'\n';
            else cout<<a[t.first]<<" "<<a[t.second]<<'\n';
        }
        else{
            x=lower_bound(a,a+len,x)-a;
            y=lower_bound(a,a+len,y)-a;
            modify(1,x,y,k);
        }
    }
}

Problem - 85D - Codeforces

向集合里add，del数
第三个操作，求将集合里的数排序后的∑(a[i%5==3])

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

/*
---i---|--j----
   i    cnt[ls]+j
   i是ls最后一个mod5的点，j是rs第一个mod5的点
   所以他们之间距离mod5==0
   cnt+j-i=0
   j=i-cnt%5
*/
#include<bits/stdc++.h>
#define int long long
#define ls u<<1
#define rs u<<1|1
using namespace std;
const int N=1e5+10;
int T,n,m,len,a[N];
string op[N];
int x[N];
int cnt[N*4],sum[N*4][5];
void pushup(int u){
    cnt[u]=cnt[ls]+cnt[rs];
    for(int i=0;i<5;i++){
        int j=((i-cnt[ls])%5+5)%5;
        sum[u][i]=sum[ls][i]+sum[rs][j];
    }
}
void modify(int u,int x,int op=1,int l=0,int r=len-1){
    if(l==r){
        cnt[u]+=op;
        sum[u][1]+=op*a[x];
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify(ls,x,op,l,mid);
    else modify(rs,x,op,mid+1,r);
    pushup(u);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>op[i];
        if(op[i]=="add"){
            cin>>x[i];
            a[m++]=x[i];
        }
        if(op[i]=="del")cin>>x[i];
    }
    sort(a,a+m);
    len=unique(a,a+m)-a;
    // for(int i=0;i<len;i++)cout<<"a["<<i<<"]="<<a[i]<<'\n';
    for(int i=1;i<=n;i++){
        if(op[i]=="add"){
            int t=lower_bound(a,a+len,x[i])-a;
            modify(1,t,+1);
        }
        if(op[i]=="del"){
            int t=lower_bound(a,a+len,x[i])-a;
            modify(1,t,-1);
        }
        if(op[i]=="sum")cout<<sum[1][3]<<'\n';
    }
}

10月1号

Codeforces Beta Round #87 (Div. 1 Only)E

n个路m个任务，修建第i个路有ci的代价，如果l-r的路都是修建好的会得到x的利润，求最大利润
设f【i】表示前i段路的最大代价
这道题最难的就是状态转移的设计
建议自己不看题解再做一遍，挺经典的值得三刷

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
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef pair<int,int>PII;
#define l first
#define v second
#define ls u<<1
#define rs u<<1|1
#define int long long
int f[N],lazy[N*4],sum[N*4],c[N];
int n,m;
vector<PII>v[N];
void pushdown(int u){
    sum[ls]+=lazy[u],lazy[ls]+=lazy[u];
    sum[rs]+=lazy[u],lazy[rs]+=lazy[u];
    lazy[u]=0;
}
int pushup(int u){
    sum[u]=max(sum[ls],sum[rs]);
}
void modify(int u,int ql,int qr,int v,int l=0,int r=n){
    if(ql>r||qr<l)return;
    if(ql<=l&&r<=qr){
        sum[u]+=v;
        lazy[u]+=v;
        return;
    }
    pushdown(u);
    int mid=l+r>>1;
    modify(ls,ql,qr,v,l,mid);
    modify(rs,ql,qr,v,mid+1,r);
    pushup(u);
}
int query(int u,int ql,int qr,int l=0,int r=n){
    if(ql>r||qr<l)return 0;
    if(ql<=l&&r<=qr)return sum[u];
    int mid=l+r>>1;
    pushdown(u);
    return max(query(ls,ql,qr,l,mid),query(rs,ql,qr,mid+1,r));
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=m;i++){
        int l,r,x;
        cin>>l>>r>>x;
        v[r].push_back({l,x});
    }
    for(int i=1;i<=n;i++){
        modify(1,0,i-1,-c[i]);
        for(auto &[l,x]:v[i]){
            modify(1,0,l-1,x);
        }
        f[i]=max(query(1,0,i-1),f[i-1]);
        modify(1,i,i,f[i]);
    }
    cout<<f[n];
}

Codeforces Beta Round #28 (Codeforces format)B

a【】=1 ~ n
给一个d数组表示第i个数字可以跟距离为d【i】的数字交换
给一个b数组表示a是否可以变成b
考点–flyod求闭包

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
#include<bits/stdc++.h>
using namespace std;
const int N=110;
typedef pair<int,int>PII;
int d[N],b[N],f[N][N],n;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>d[i];
    for(int i=1;i<=n;i++){
        f[i][i]=1;
        if(i-d[i]>=1)f[i][i-d[i]]=f[i-d[i]][i]=1;
        if(i+d[i]<=n)f[i][i+d[i]]=f[i+d[i]][i]=1;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]|=f[i][k]&f[k][j];
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(f[i][b[i]]==0){
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
}

Codeforces Beta Round #36E

欧拉路径是找到一条路径覆盖所有的边
这道题是让你用两条路径覆盖所有的边求方案

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2*N;
int m,p[N],h[N],e[M],ne[M],vis[M],idx,d[N],ans[M],c;
map<int,int>mp;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int x){
    if(p[x]==x)return x;
    return p[x]=find(p[x]);
}
void dfs(int u){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(vis[i])continue;
        vis[i]=vis[i^1]=1;
        dfs(j);
        ans[++c]=i;
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>m;
    if(m==1){cout<<"-1";return 0;}
    for(int i=0;i<=10000;i++)p[i]=i,h[i]=-1;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
        d[a]++,d[b]++;
        if(find(a)==find(b))continue;
        p[find(a)]=find(b);
    }
    //用两条路径覆盖全部的边
    /*
    回顾欧拉路径的定义：
    有向图：有两个点出度=入度+1，入度=出度+1，其他点出度=入度
    无向图：有两个点度数为奇数，其他点度数为偶数
    
    回顾欧拉回路的定义：
    有向图：出度=入度
    无向图：所有度数均为偶数
    
    那么这道题就是两个欧拉路径无向图，所以点度数为奇数个数只能是{0，2，4}
    分类讨论如果是1个连通分量或者两个连通分量
    
    上述分析均不考虑孤立点
    */
    int cnt=0;
    for(int i=1;i<=10000;i++){
        if(d[i]==0)continue;
        mp[find(i)]+=d[i]&1;
        if(find(i)==i)cnt++;
    }
    if(cnt>2){cout<<"-1";return 0;}
    if(cnt==2){//两个欧拉路径
        for(auto t:mp){
            if(t.second==0||t.second==2)continue;
            cout<<"-1";
            return 0;
        }
        for(auto t:mp){
            int u=t.first;
            for(int i=1;i<=10000;i++){
                if(find(i)==t.first&&d[i]&1)
                {u=i;break;}
            }
            c=0;
            dfs(u);
            cout<<c<<'\n';
            for(int i=1;i<=c;i++)cout<<ans[i]/2+1<<"\n";
        }
    }
    if(cnt==1){
        auto t=*mp.begin();
        if(t.second==0||t.second==2){
            int u=t.first;
            for(int i=1;i<=10000;i++){
                if(find(i)==t.first&&d[i]&1)
                {u=i;break;}
            }
            c=0;
            dfs(u);
            cout<<1<<'\n';
            cout<<ans[1]/2+1<<'\n';
            cout<<c-1<<'\n';
            for(int i=2;i<=c;i++)cout<<ans[i]/2+1<<" ";
        }
        else if(t.second==4){
            vector<int>ji;
            for(int i=1;i<=10000;i++){
                if(d[i]==0)continue;
                if(d[i]&1)ji.push_back(i);
            }
            add(ji[0],ji[1]),add(ji[1],ji[0]);
            c=0;
            dfs(ji[2]);
            int x;
            for(int i=1;i<=c;i++){
                // cout<<"ans["<<i<<"]="<<ans[i]<<" ";
                if(ans[i]>=2*m)x=i;
            }
            // cout<<'\n';
            // return 0;
            cout<<x-1<<'\n';
            for(int i=1  ;i< x;i++)cout<<ans[i]/2+1<<" ";
            cout<<'\n';
            cout<<c-x<<'\n';
            for(int i=x+1;i<=c;i++)cout<<ans[i]/2+1<<' ';
        }
        else{
            cout<<-1;
            return 0;
        }
        
    }
    
}

Codeforces Beta Round #88C

找一个len=3的环

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
#include<bits/stdc++.h>
using namespace std;
const int N=5500;
int n;
char s[N][N];
int to[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i]+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s[i][j]=='1')to[j]=i;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            //j-i i->x x->j
            if(s[j][i]=='1'&&s[i][to[j]]=='1'){
                cout<<j<<" "<<i<<" "<<to[j];
                return 0;
            }
        }
    }
    cout<<-1;
}

10月8号

flyod

求从1号点到n号点的最短路径，每次可以选择一条边a-b断开并connect a-c

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=550,M=1e6+10;
int T,n,f[N][N],m,a[M],b[M],c[M];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
            if(i==j)f[i][j]=0;
            else f[i][j]=1e9;
        }
        for(int i=1;i<=m;i++){
            cin>>a[i]>>b[i]>>c[i];
            f[a[i]][b[i]]=f[b[i]][a[i]]=1;
        }
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
                }
            }
        }
        int ans=1e18;
        for(int i=1;i<=m;i++){
            int u=a[i];
            int v=b[i];
            int w=c[i];
            ans=min(ans,w*(f[1][u]+1+f[v][n]));
            ans=min(ans,w*(f[1][v]+1+f[u][n]));
            for(int x=1;x<=n;x++){
                ans=min(ans,w*(f[1][x]+f[x][n]+min(f[u][x],f[v][x])+2));
            }
        }
        cout<<ans<<'\n';
    }
}

单调栈优化dp

将序列分成k段（k=1~n）
每一段的权重为max ai
求min ∑序列分成k段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int N=8080;
int f[N][N],stk[N],top,sum[N],n,a[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)f[0][i]=1e9,sum[i]=1e9;
    for(int i=1;i<=n;i++){
        top=0;
        f[i][top]=1e9;
        for(int j=i;j<=n;j++){
            sum[j]=f[i-1][j-1];
            while(top&&a[stk[top]]<=a[j]){
                sum[j]=min(sum[j],sum[stk[top--]]);
            }
            
            f[i][j]=min(f[i][stk[top]],sum[j]+a[j]);
            stk[++top]=j;
        }
        cout<<f[i][n]<<'\n';
    }
}

mex on tree

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>g[N];
int n,a[N],sz[N],ans[N],f[N];
/*
找到最大连通块使得mex=0~n
*/
void dfs(int u,int fa=0){
    sz[u]=1;
    f[u]=a[u];
    int ma=0;
    for(auto j:g[u]){
        if(j==fa)continue;
        dfs(j,u);
        ma=max(ma,sz[j]);
        f[u]=min(f[u],f[j]);
        sz[u]+=sz[j];
    }
    if(a[u]==0){ans[0]=ma;return;}
    if(f[u]<a[u])ans[a[u]]=0;
    else ans[a[u]]=n-sz[u];
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    int r=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==0)r=i;
    }
    for(int i=2;i<=n;i++){
        int fa;
        cin>>fa;
        g[fa].push_back(i);
        g[i].push_back(fa);
    }
    dfs(r);
    for(int k=0;k<n;k++)cout<<ans[k]<<" ";
    cout<<n;
}

直方图最大面积

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
class Solution {
public:
static const int N=2e5+10;
int w[N],ans,stk[N],ls[N],rs[N],sz[N],n;
void build(){
    for(int i=1;i<=n;i++)ls[i]=rs[i]=sz[i]=0;
    int top=0;
    for(int i=1;i<=n;i++){
        int k=top;
        while(k&&w[i]<=w[stk[k]])k--;
        if(k)rs[stk[k]]=i;
        if(k<top)ls[i]=stk[k+1];
        stk[++k]=i,top=k;
    }
}
void dfs(int u){
    if(ls[u])dfs(ls[u]);
    if(rs[u])dfs(rs[u]);
    sz[u]=sz[ls[u]]+sz[rs[u]]+1;
    ans=max(ans,sz[u]*w[u]);
}

    int largestRectangleArea(vector<int>& h) {
        n=h.size();
        for(int i=1;i<=n;i++)w[i]=h[i-1];
        build();
        dfs(stk[1]);
        return ans;
    }
};

笛卡尔树

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+10;
int n,a[N],b[N],ls[N],rs[N],sz[N],ans=-1e18,stk[N];
void build(){
    int top=0;
    for(int i=1;i<=n;i++){
        int k=top;
        while(k&&a[i]<=a[stk[k]])k--;
        if(k)rs[stk[k]]=i;
        if(k<top)ls[i]=stk[k+1];
        stk[++k]=i,top=k;
    }
}
int lmax[N],rmax[N];
int lmin[N],rmin[N];
int sum[N];
void dfs(int u){
    if(ls[u])dfs(ls[u]);
    if(rs[u])dfs(rs[u]);
    sum[u]=sum[ls[u]]+b[u]+sum[rs[u]];
    lmax[u]=max(lmax[ls[u]],sum[ls[u]]+b[u]+lmax[rs[u]]);
    lmin[u]=min(lmin[ls[u]],sum[ls[u]]+b[u]+lmin[rs[u]]);
    rmax[u]=max(rmax[rs[u]],sum[rs[u]]+b[u]+rmax[ls[u]]);
    rmin[u]=min(rmin[rs[u]],sum[rs[u]]+b[u]+rmin[ls[u]]);
    if(a[u]>0)ans=max(ans,a[u]*(rmax[ls[u]]+b[u]+lmax[rs[u]]));
    else ans=max(ans,a[u]*(rmin[ls[u]]+b[u]+lmin[rs[u]]));
    
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    build();
    dfs(stk[1]);
//     cout<<"a["<<stk[1]<<"]="<<a[stk[1]]<<'\n';
    cout<<ans;
}

Life is a Game

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
#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=2e5+10;
int f[N][21],ma[N][21],a[N],b[N],n,m,q,u,k,p[N];
struct node{
    int u,vv,w;
    bool operator<(const node&t){
        return w<t.w;
    }
};
vector<node>v;
vector<int>g[N];
int find(int x){
    if(p[x]==x)return p[x];
    return p[x]=find(p[x]);
}
void dfs(int u,int fa=0){
    f[u][0]=fa;
    for(int i=1;i<=20;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(auto j:g[u]){
        dfs(j,u);
        a[u]+=a[j];
    }
}
void dfs2(int u,int fa=0){
    ma[u][0]=b[fa]-a[u];
    for(int i=1;i<=20;i++){
        ma[u][i]=max(ma[u][i-1],ma[f[u][i-1]][i-1]);
    }
    for(auto j:g[u]){
        dfs2(j,u);
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n+m;i++)p[i]=i;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--){
        int u,vv,w;
        cin>>u>>vv>>w;
        v.push_back({u,vv,w});
    }
    sort(v.begin(),v.end());
    for(auto t:v){
        int u=t.u;
        int v=t.vv;
        int w=t.w;
        u=find(u),v=find(v);
        if(u==v)continue;
        n++;
        b[n]=w;
        p[u]=p[v]=n;
        g[n].push_back(u),g[n].push_back(v);
    }
    dfs(n);
    b[0]=2e9+1;
    dfs2(n);
    while(q--){
        cin>>u>>k;
        for(int i=20;i>=0;i--){
            if(k>=ma[u][i])u=f[u][i];
        }
        cout<<a[u]+k<<'\n';
    }
}

华华开始学信息学

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,tr[N],m,d[N];
void add(int x,int c){
    for(int i=x;i<=n;i+=i&-i)tr[i]+=c;
}
int sum(int x){
    if(x==0)return 0;
    int ans=0;
    for(int i=x;i;i-=i&-i)ans+=tr[i];
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int D,K;
            cin>>D>>K;
            if(D>400)for(int i=D;i<=n;i+=D)add(i,K);
            if(D<=400) d[D]+=K;
        }
        else{
            int l,r;
            cin>>l>>r;
            int ans=sum(r)-sum(l-1);
            for(int i=1;i<=400;i++)ans+=(r/i-(l-1)/i)*d[i];
            cout<<ans<<'\n';
        }
    }
}

牛客挑战赛32E树上逆序对

算逆序对的时候，按照权值从小到大的dfs序去插入和查询计数
本题其实就是当把一个顺逆序对，某个权值变负所造成的影响
对祖宗造成影响 ，对儿子也造成影响
开两课树分别计算，那么贡献就是01背包的放与不放
注意细节祖宗树，插入的时候就是dfn[u],1 和 dfn[u]+sz[u]-1,-1
查询的时候就是query dfn[u]

子节点树，插入的时候dfn 1，查询的时候就是dfn到dfn+sz-1

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
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1 
using namespace std;
const int N=1e5+10;
int n,dfn[N],sz[N];
vector<int>g[N];
struct tree{
    int a[N*4];
    tree(){memset(a,0,sizeof a);}
    void pushup(int u){
        a[u]=a[ls]+a[rs];
    }
    void modify(int u,int x,int v,int l=0,int r=n){
        if(l==r){
            a[u]+=v;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid)modify(ls,x,v,l,mid);
        else modify(rs,x,v,mid+1,r);
        pushup(u);
    }
    int query(int u,int ql,int qr,int l=0,int r=n){
        if(ql<=l&&r<=qr)return a[u];
        if(ql>r||qr<l)return 0;
        int mid=(l+r)>>1;
        return query(ls,ql,qr,l,mid)+query(rs,ql,qr,mid+1,r);
    }
    
}T[2];
struct node{
    int v,i;
}a[N];
int idx,o[N];
void dfs(int u,int fa=0){
    dfn[u]=++idx;
    sz[u]=1;
    for(auto j:g[u]){
        if(j==fa)continue;
        dfs(j,u);
        sz[u]+=sz[j];
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].v;
        a[i].i=i;
    }
    sort(a+1,a+1+n,[&](node x,node y){
        return x.v<y.v;
    });
//     for(int i=1;i<=n;i++){
//         cout<<"a["<<i<<"]="<<a[i].i<<'\n';
//     }
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    bitset<30001>ans;
    ans[0]=1;
    for(int i=1;i<=n;i++){
        int u=a[i].i;
        int x=T[0].query(1,1,dfn[u]);
        int y=T[1].query(1,dfn[u],dfn[u]+sz[u]-1);
        ans=ans<<x | ans<<y;
        T[0].modify(1,dfn[u],1);
        T[0].modify(1,dfn[u]+sz[u],-1);
        T[1].modify(1,dfn[u],1);
    }
    int q;
    cin>>q;
    while(q--){
        int k;
        cin>>k;
        if(ans[k])cout<<"Orz"<<'\n';
        else cout<<"QAQ"<<'\n';
    }
}
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
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n,a[N],dfn[N],sz[N],o[N],idx;
struct node{
    int tr[N];
    void add(int x,int c){
        if(x==0)return;
        for(int i=x;i<=n;i+=i&-i)tr[i]+=c;
    }
    int sum(int x){
        int ans=0;
        for(int i=x;i;i-=i&-i)ans+=tr[i];
        return ans;
    }
}T[2];
vector<int>g[N];
void dfs(int u,int fa=0){
    dfn[u]=++idx;
    sz[u]=1;
    for(auto j:g[u]){
        if(j==fa)continue;
        dfs(j,u);
        sz[u]+=sz[j];
    }
    
}
bool cmp(int &i,int &j){
    return a[i]<a[j];
}
bitset<30001>ans;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],o[i]=i;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    ans[0]=1;
    dfs(1);
    sort(o+1,o+1+n,cmp);
    //按照权值大小排序，求每个节点有多少个祖先，多少个儿子
    for(int i=1;i<=n;i++){
        int u=o[i];
        int v1=T[0].sum(dfn[u]-1);//祖先
        int v2=T[1].sum(dfn[u]+sz[u]-1)-T[1].sum(dfn[u]-1);//儿子
        ans=ans<<v1|ans<<v2;
        T[0].add(dfn[u],1),T[0].add(dfn[u]+sz[u]-1,-1);
        T[1].add(dfn[u],1);
    }
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        if(ans[x])cout<<"Orz"<<'\n';
        else cout<<"QAQ"<<'\n';
    }
}

倍增并查集

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
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,p[N*21],l,r,x,y,t;
int find(int x){
    if(p[x]==x)return x;
    return p[x]=find(p[x]);
}
int get(int i,int j){
    return j*N+i;
}
void merge(int a,int b){
    p[find(a)]=find(b);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int j=0;j<20;j++)for(int i=1;i<=n+n;i++)p[get(i,j)]=get(i,j);
    for(int i=1;i<=n;i++)merge(get(i,0),get(2*n-i+1,0));
    while(m--){
        cin>>l>>r;
        int len=r-l+1;
        int R=n*2-r+1;
        for(int j=19;j>=0;j--){
            if(len>>j&1)merge(get(l,j),get(R,j)),l+=1<<j,R+=1<<j;
        }
    }
    for(int j=19;j>=1;j--){
        for(int i=1;i<=n*2;i++){
            x=get(i,j);
            if(find(x)==x)continue;
            x=find(x);
            t=x%N;
            x=get(t,j-1);
            y=get(i,j-1);
            merge(x,y);
            x=get(t+(1<<j-1),j-1);
            y=get(i+(1<<j-1),j-1);
            merge(x,y);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(find(i)==find(n-i+1))ans++;
    }
    if(ans==n)cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';
    cout<<ans;
}

天梯赛L3-2

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
int n,a[N],tr[N],r,ans,sz[N],s1,s2,s=1,f[N];
vector<int>g[N];
void add(int x,int c){
    for(int i=x;i<=n;i+=i&-i)tr[i]+=c;
}
int sum(int x){
    int ans=0;
    for(int i=x;i;i-=i&-i)ans+=tr[i];
    return ans;
}
void dfs(int u,int fa=0){
    sz[u]=1;
    add(u,1);
    s1=(s1+sum(n)-sum(u))%mod;//祖宗有多少个比我大的
    int cnt=0;
    for(auto j:g[u]){
        if(j==fa)continue;
        dfs(j,u);
        cnt++;
        sz[u]+=sz[j];
    }
    s=(s*f[cnt])%mod;//子树个数的阶乘
    add(u,-1);
    s2=(s2+n-sz[u]-sum(n))%mod;//跟我非祖宗关系的个数
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>r;
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i%mod;
    for(int i=1;i<=n;i++)a[i]=n-i+1;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(r);
    ans=s1*s+(s2*s%mod*(mod+1)/4);
    cout<<ans%mod;
}
文章作者: 胡耀文
文章链接: https://hyw200199.github.io/2022/09/30/2022-guo-qing-acm-shua-ti-xun-lian/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 胡耀文 !
训练 知乎
赏