Codeforces 每日一练 1213G+961E+1282B2

（都是多解题啊QAQ，我就只写一种了，其实是不会其他的

1213G Path Queries

传送门
题意：一棵节点数为n的边权树，m次询问，每次回答最大权值小于q的简单路径数目。
考虑到符合询问的路径一定不包含权值大于q的边，可以考虑用先把询问排序，然后边排序，依次加边的离线做法。
对于已经加的边，形成的是一个个连通块，假设某连通块的大小为n，那么它对答案的贡献就是$C_{n}^{2}$，合并过程中先减去两个连通块的贡献，合并后加上整体的贡献。
带权并查集＋离线即可AC。

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
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 200005
#define ll long long
#define int long long
int q[maxn],tmp[maxn],sz[maxn],f[maxn];
struct edge{
    int u,v,w;
}e[maxn];
ll ans=0;
int findfa(int x){
    if(f[x]==x)return x;
    else f[x]=findfa(f[x]);
    return f[x];
}
void mergefa(int a,int b){
    int fa=findfa(a),fb=findfa(b);
    if(fa!=fb){
        if(sz[fa]<sz[fb])swap(fa,fb);
        f[fb]=fa;
        ans-=sz[fa]*(sz[fa]-1)/2;
        ans-=sz[fb]*(sz[fb]-1)/2;
        sz[fa]+=sz[fb];
        ans+=sz[fa]*(sz[fa]-1)/2;
    }
}
bool cmp(edge a,edge b){
    return a.w<b.w;
}
map<int,int>mp;
signed  main(){
    IOS
    int n,m;
    cin>>n>>m;
    for (int j = 1; j <=n ; ++j) {
        f[j]=j;
        sz[j]=1;
    }
    for (int i = 0; i <n-1 ; ++i) {
        int u,v,wt;
        cin>>u>>v>>wt;
        e[i].u=u;
        e[i].v=v;
        e[i].w=wt;
    }
    for (int i = 0; i <m ; ++i) {
        cin>>q[i];
        tmp[i]=q[i];
    }
    sort(e,e+n-1,cmp);
    sort(q,q+m);
    for (int i = 0,j=0; i <m ; ++i) {
        while(j<n-1&&e[j].w<=q[i]){
            mergefa(e[j].u,e[j].v);
            j++;
        }
        mp[q[i]]=ans;
    }
    for (int i = 0; i <m ; ++i) {
        cout<<mp[tmp[i]]<<" ";
    }
    return 0;
}

关于并查集＋离线的另一道题：洛谷P1197 [JSOI2008]星球大战
其实这道题还能点分治去写，或者二分＋并查集的在线做法。
分治走这里
二分＋并查集

961E Tufurama

传送门
题意：一个电视连续剧有n季（2e5季真的折磨哦 ），每季有a[i]集，询问点对<x,y>满足第y季第x集与第x季第y集同时存在的数目。
首先尝试把题意简化，若要满足要求一定有a[x]>=y和a[y]>=x，为了避免重复计算，加上y>x，那么就相当于在x+1a[x]之间找满足a[y]>=x的季数，同时由于季数一定小于等于n，那么如果a[x]>=n，可以把a[x]直接换成n，把数据范围缩小到2e5。
明白题意后就是做法了，可以树状数组也可以权值线段树，但正好没学过主席树，就去学了学，然后用主席树水过了这道题。
（如果你像我一样没学过主席树，可以这边走：传送门
那么我们建好树之后只需要每次去找i+1a[i]里在区间[i,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
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
123
124
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 200005
#define ll long long
int a[maxn];
ll b[maxn];
struct persistent_seg_tree
{
    struct data
    {
        int sum;
        data() :sum(0) {}
    };
    struct node
    {
        int l, r;
        data d;
        node() :l(0), r(0) {}
    };
    vector<node> nodes;
    vector<int> roots;
    int sz;

    void up(int id)
    {
        nodes[id].d.sum = nodes[nodes[id].l].d.sum + nodes[nodes[id].r].d.sum;
    }
    int newnode(int cpy)
    {
        int id = (int)nodes.size();
        node tmp = nodes[cpy];
        nodes.push_back(tmp);
        return id;
    }
    int add(int tp, int tl, int tr, int i, int v)
    {
        int id = newnode(tp);
        if (tl + 1 >= tr)
        {
            nodes[id].d.sum += v;
            return id;
        }
        int tmid = (tl + tr) / 2;
        if (i < tmid)
        {
            int nid = add(nodes[id].l, tl, tmid, i, v);
            nodes[id].l = nid;
        }
        else
        {
            int nid = add(nodes[id].r, tmid, tr, i, v);
            nodes[id].r = nid;
        }
        up(id);
        return id;
    }
    int getsum(int tp, int tl, int tr, int l, int r)
    {
        if (l <= tl && tr <= r)
        {
            return nodes[tp].d.sum;
        }
        int tmid = (tl + tr) / 2;
        int sum = 0;
        if (l < tmid)
        {
            sum += getsum(nodes[tp].l, tl, tmid, l, r);
        }
        if (r > tmid)
        {
            sum += getsum(nodes[tp].r, tmid, tr, l, r);
        }
        return sum;
    }
    // interface
    void init(int range, int root_size) // 数组大小[0, range)，操作次数
    {
        sz = range;
        nodes.clear();
        roots.clear();
        nodes.reserve(root_size * (int)(log(sz * 2.0) / log(2.0) + 1.01));
        nodes.push_back(node());
        roots.reserve(root_size + 1);
        roots.push_back(0);
    }
    void add(int pos, int v)
    {
        int last = roots.back();
        roots.push_back(add(last, 0, sz, pos, v));
    }
    int getsum(int t, int l, int r)
    {
        if (t <= 0) return 0;
        if (r < l) return 0;
        if (t >= (int)roots.size()) t = (int)roots.size() - 1;
        return getsum(roots[t], 0, sz, l, r + 1);
    }
}tree;
signed  main(){
    IOS
    int n;
    cin>>n;
    ll tmp=n;
    int ma=-1;
    for (int i = 1; i <=n ; ++i) {
        cin>>b[i];
        a[i]=min(b[i],tmp);
        ma=max(ma,a[i]);
    }
    tree.init(ma+1,4*n);
    for (int i = 1; i <=n ; ++i) {
        tree.add(a[i],1);
    }
    ll ans=0;
   for (int i = 1; i <=n ; ++i) {
        int r=min(n,a[i]);
        int l=i+1;
        if(r>=l)ans+=tree.getsum(r,i,n+1)-tree.getsum(l-1,i,n+1);
    }
    cout<<ans;
    return 0;
}

如果你不想写主席树，简单的权值线段树也是可以的，贴大佬博客了：权值线段树传送门

1282B2 K for the Price of One (Hard Version)

传送门
题意：n个商品，每个加个a[i]，你携带了金额为p的money，正好碰上商店的活动，购买一个商品可以选择k-1个加个小于等于它的商品免费拿走（0或k-1二选一，不能选其他数目），最后你能买多少物品。
首先把商品按加个排序，明显买连续的前m个是最优的，假设购买了前k个，而后面的从k+2开始购买，那我们把后面的整体前移，数目不变，总价减少了，说明购买连续的前m个是最优的。
那么就可以写dp转移了，记录买到第i个要多少钱，对于前k-1个，由于不能白嫖，只能连续买，dp[i]=dp[i-1]+a[i]，而对于之后的，肯定怎么省钱怎么来，dp[i]=dp[i-k]+a[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
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define maxn 200005
#define ll long long
ll a[maxn],p;
int n,k;
ll dp[maxn];
signed  main(){
    IOS
    int t;
    cin>>t;
    while(t--) {
        cin >> n >> p >> k;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        memset(dp,0, sizeof(dp));
        sort(a+1,a+1+n);
        for (int i = 1; i <=n ; ++i) {
            if(i<k)dp[i]=dp[i-1]+a[i];
            else dp[i]=dp[i-k]+a[i];
        }
        int ans=0;
        for (int j = 1; j <=n ; ++j) {
            if(dp[j]<=p){
                ans=j;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}