AT_abc413

又是战犯的一周啊。
再见宣言真好听。
A.Content Too Large

translation:

判断是否有 \(\sum_{i=1}^n A_i\le M\)。

无脑题，不给代码了。赛时除了手速有点慢以外没啥别的问题。
B.cat 2

translation:

给定 \(n\) 个字符串 \(S_1,S_2,\dots,S_n\)，任选两个不同的字符串前后连接可以得到 \(n(n-1)\) 个字符串。求这 \(n(n-1)\) 个字符串中有多少个不同的字符串。

\(n\le 100\)，所以对照题面逐句实现即可，拿个 set 去下重就没有然后了。不给代码。
C.Large Queue

translation:

有一个队列，初始为空。有 \(q\) 次操作，如下：
1 c x：在队列末尾插入 \(c\) 个 \(x\)。
2 k：弹出队首的 \(k\) 个数，并输出他们的和。

逐句实现显然不现实。注意到对于某个数 \(x\)，如果我们知道了它在需要弹出的数中出现的次数，那么可以 \(O(1)\) 求贡献。于是记录每个数插入后的结尾位置，每次相当于查询一段区间的和。可以通过 lower_bound 出边界处的两个元素来计算。中间的数暴力扫一遍，由于查询的区间是连续且不重合的，所以每个数最多会被暴力扫一遍，时间复杂度正确，为 \(O(n\log n)\)。
code

[code]#includeusing namespace std;#define int long longint n,ed[200005],x[200005],fr=1,tot;signed main(){        cin>>n;        while(n--){                int op;cin>>op;                if(op==1){                        int c;tot++;                        cin>>c>>x[tot];                        ed[tot]=ed[tot-1]+c;                }                else{                        int k;cin>>k;                        int l=lower_bound(ed+1,ed+tot+1,fr)-ed;                        int r=lower_bound(ed+1,ed+tot+1,fr+k-1)-ed;                        int ans=(ed[l]-fr+1)*x[l];                        for(int i=l+1;i