省流：ABCDEF，G 感觉有点难了而且慢速选手无法完成 www，rk280。

A,B,C

略去，不过这里需要特别提醒一下 C 题，显然有结论，就是我们锁上门后显然不会再打开，否则一定不优，开操作和闭操作各自至多进行一次。要能够把所有门都变为锁状态的充要条件是：在完成所有开操作之后，仍然处于打开状态的锁的编号集合必须是形如{i∣X≤i≤Y}\{i\mid X\le i\le Y\} 的一个连续区间（并满足X≤R,;R−1≤YX\le R,;R-1\le Y）。令Li=0L_i=0 的最小下标为xx、最大下标为yy。当x≤R−1x\le R-1 时，只需进行使得门x,x+1,…,R−1x,x+1,\dots,R-1 的钥匙全部打开的操作；当y≥Ry\ge R 时，只需进行使得门R,R+1,…,yR,R+1,\dots,y 的钥匙全部打开的操作，也可以暴力模拟，时间复杂度O(n)O(n)。

D

用一个堆维护当前在餐馆内的人，模拟即可，时间复杂度O(nlog⁡n)O(n\log 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
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=3e5+15;
struct Node{
    int a,b,c,id;

}a[MN];
struct PNode{
    int a,b,c,id,tim;

    PNode(Node x,int t){
        a=x.a,b=x.b,c=x.c,id=x.id,tim=t;
    }

    friend bool operator>(const PNode &x,const PNode &y){
        return x.tim>y.tim;
    }
};
int n,K,T,pcnt,ans[MN];
priority_queue<PNode,vector<PNode>,greater<PNode>> q;

bool cmp(Node x,Node y){
    return x.a<y.a;
}

signed main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b>>a[i].c;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    ans[a[1].id]=a[1].a;
    T=a[1].a;
    pcnt=a[1].c;
    q.push(PNode(a[1],T+a[1].b));
    for(int i=2;i<=n;i++){
        if(pcnt+a[i].c>K){
            while(!q.empty()&&pcnt+a[i].c>K){
                auto tp=q.top();
                q.pop();
                T=tp.tim;
                pcnt-=tp.c;
            }
            T=max(T,a[i].a);
            ans[a[i].id]=T;
            pcnt+=a[i].c;
            q.push(PNode(a[i],T+a[i].b));
        }else{
            pcnt+=a[i].c;
            T=max(T,a[i].a);
            ans[a[i].id]=T;
            q.push(PNode(a[i],T+a[i].b));
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<'\n';
    }

    return 0;
}

E

显然的想法就是历史和线段树加扫描线，属于子区间计数的经典应用。

不过显然这是求和，考虑贡献法将贡献拆到每一个位置上，考虑[L,R][L,R] 的区间内有多少个子区间可以让aia_{i} 贡献上，答案是(R−i+1)(i−L+1)(R-i+1)(i-L+1) 次，故答案就是对于[L,R][L,R] 区间求∑i∈[L,R](R−i+1)(i−L+1)ai\sum\limits_{i\in [L,R]} (R-i+1)(i-L+1)a_{i} 即可，注意到显然可以拆开，拆开后会出现i2aii^2 a_{i}、iaiia_{i} 和aia_{i} 这三项的前缀和，维护即可，时间复杂度O(n)O(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
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e5+15;
int sumx[MN],sumy[MN],sumz[MN],a[MN],n,q;

signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sumx[i]=a[i];
        sumy[i]=i*a[i];
        sumz[i]=i*i*a[i];
    }
    for(int i=1;i<=n;i++){
        sumx[i]+=sumx[i-1];
        sumy[i]+=sumy[i-1];
        sumz[i]+=sumz[i-1];
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        int X = sumx[r]-sumx[l-1];
        int Y = sumy[r]-sumy[l-1];
        int Z = sumz[r]-sumz[l-1];
        cout << (l+r)*Y+(r-l+1)*X-l*r*X-Z << '\n';
    }
    return 0;
}

F

正着直接状压枚举很难，因为可能会算重很多。正难则反容斥，直接状压加二项式反演。不妨设fkf_{k} 表示恰好有kk 个物种同时爆发的年份数，gkg_{k} 表示至少有kk 个物种同时爆发的年份数，显然有二项式反演公式：

gk=∑i=kn(ik)fi⇔fk=∑i=kn(−1)i−k(ik)gig_{k}=\sum\limits_{i=k} ^n \binom{i}{k} f_{i} \Leftrightarrow f_{k}=\sum\limits_{i=k}^n (-1)^{i-k} \binom{i}{k} g_{i}

其中nn 就是题目中的物种上限。现在问题转化为至少怎么求。首先由于n≤20n\le 20 不难想到状压，然后是这个至少怎么解决呢？当然！我们可以转为钦定，我们钦定的年份必须选择，然后计算选取它们至少有多少个年份合法即可！具体的我们可以枚举非空子集SS，然后计算其lcm⁡\operatorname{lcm} 即最小公倍数，若lcm⁡≤y\operatorname{lcm}\le y，则所有是lcm⁡\operatorname{lcm} 的倍数的年份都至少包含SS 中枚举的蝉，那么有多少个倍数呢，答案就是⌊Ylcm⁡(S)⌋\lfloor \dfrac{Y}{\operatorname{lcm}(S)} \rfloor，然后根据上面的公式反演容斥一下即可，时间复杂度为O(n2n)O(n2^n )。

话说为什么我预处理组合数炸了非要让我现算呢？还有记得开 __int128。

同时这里说明，二项式反演公式描述的是至少与恰好之间的关系，与具体ff 与gg 如何计算无任何关系，只要满足上面的公式就可以。

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>
#define int long long
#define lint __int128
using namespace std;
constexpr int MN=25;
int n,m;
lint a[MN],ans,Y,pw[MN],inv[MN];

signed main(){
    read(n,m,Y);
    for(int i=0;i<n;i++){
        read(a[i]);
    }
    for(int s=1;s<(1<<n);s++){
        int cnt1=__builtin_popcountll(s);
        lint ret=1;
        bool flag=0;
        for(int i=0;i<n;i++){
            if((s>>i)&1){
                ret = lcm(ret,a[i]); //新c++版本默认有 lcm和gcd函数
                if(ret>Y){
                    flag=1;
                    break;
                }
            }
        }
        if(flag) continue;
        int res=Y/ret;
        if(cnt1 >= m) {
            int C=1;
            for(int i=0;i<m;i++){
                C=C*(cnt1-i)/(i+1);// C(cnt1, m)
            }
            if((cnt1-m)%2) res=-res;
            ans+=C*res;
        }
    }
    put(ans);
    return 0;
}