好久不打用小号水了一场，赛时坑坑拌拌勉强四题，以为美美上分，结果重测时卡掉了我没细想复杂度就交了的B题，这下小丑了
A. We Got Everything Covered!
直接输出n次连续前k个字母即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
cin>>_;
while (_--){
int n,k;
cin>>n>>k;
for (int i=1;i<=n;i++){
for (int j=1;j<=k;j++){
cout<<char('a'+j-1);
}
}
cout<<'\n';
}
}
B. A Balanced Problemset?
遍历sqrt(n)中所有n的因子，大于sqrt(n)的部分在遍历中直接获得，拿出那个最大的满足题意的即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;
cin>>_;
while (_--){
int n,x;
cin>>n>>x;
int ans=1;
for (int i=1;i<=sqrt(n);i++){
if (n%i==0){
if (n/i>=x) ans=max(ans,i);
if (i>=x) ans=max(ans,n/i);
}
}
cout<<ans<<'\n';
}
}
C. Did We Get Everything Covered?
顺延A题的思路，若为yes一定是出现了连续n组包含前k的字母的字符串，比如k=3，"abbbcdbbccaaccaab"中含3组包含前3个字母的块，否则即为no，考虑到分块时每块最后一个字母一定在这个块中只出现一次，则输出的串即由每块最后一个字母构成，未填充完全的块（最后一个块）则选择缺失的字母补上字符串，若最后的字符串长度不够随便补点什么就行
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 #define int long long
5
6 signed main()
7 {
8 ios::sync_with_stdio(false);
9 cin.tie(0);cout.tie(0);
10 int _=1;
11 cin>>_;
12 while (_--){
13 int n,k,m;
14 cin>>n>>k>>m;
15 string s;
16 cin>>s;
17 int cnt=0,nw=0;
18 vector <int> alp(30,0);
19 string ans="";
20 for (int i=0;i<m;i++){
21 int d=s[i]-'a';
22 if (d<k){
23 alp[d]++;
24 if (alp[d]==1){
25 nw++;
26 if (nw==k) ans+=s[i];
27 }
28 }
29 if (nw==k){
30 cnt++;
31 for (int j=0;j<30;j++) alp[j]=0;
32 nw=0;
33 }
34 }
35 if (cnt>=n) cout<<"YES"<<'\n';
36 else{
37 cout<<"NO"<<'\n';
38 for (int j=0;j<k;j++){
39 if (alp[j]==0){
40 ans+=char('a'+j);
41 break;
42 }
43 }
44 while ((int)ans.size()<n) ans+="a";
45 cout<<ans<<'\n';
46 }
47 }
48 }
D. Good Trip
数学题，每轮的期望值即为期望总和/总可能对数，总可能对数为n*(n-1)/2，期望总和为总的友谊值之和+(i-1)*E(X)，X服从参数为i，p的二项分布，i为当前轮数，p为选到一对朋友的概率
最后将每一轮的结果加起来就可以，代码部分需要乘法逆元和快速幂的前缀知识，写起来很少硬记就行
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 #define int long long
5 const int mod=1e9+7;
6
7 int qpow(int a,int n) //快速幂
8 {
9 int ans=1;
10 while (n){
11 if (n&1) ans=ans*a%mod;
12 a=a*a%mod;
13 n>>=1;
14 }
15 return ans;
16 }
17
18 signed main()
19 {
20 ios::sync_with_stdio(false);
21 cin.tie(0);cout.tie(0);
22 int _=1;
23 cin>>_;
24 while (_--){
25 int n,m,k;
26 cin>>n>>m>>k;
27 if (m==0){
28 cout<<0<<'\n';
29 continue;
30 }
31 int sum=0;
32 for (int i=1;i<=m;i++){
33 int a,s,d;
34 cin>>a>>s>>d;
35 sum+=d;
36 sum%=mod;
37 }
38 int ans=0;
39 int al=n*(n-1)/2%mod;
40 int p=m*qpow(al,mod-2)%mod; //（乘法逆元，一般不用考虑互质）
41 for (int i=1;i<=k;i++){
42 ans=(ans+sum)%mod+(i-1)*p%mod;
43 ans%=mod;
44 }
45 ans=ans*qpow(al,mod-2)%mod;
46 cout<<ans<<'\n';
47 }
48 }
E. Space Harbour
考虑离线处理，因为在线处理需要随时寻找插入点之前的港口和之后的港口来更新v和d，我不会在线处理这东西，所以用双向链表先存下所有出现过的港口，再逆序遍历询问，op=1时删除链表结点，op=2时储存答案，最后输出即可
答案获取考虑线段树，每个节点存其v值总和、d值总和，和答案的总和，遍历1~n所有的点做预处理，之后删除港口x为区间修改，通过上面的链表可以快速获取左侧最近港口L和右侧最近港口R的信息，(L,x]区间每个值的d改变R.idx-x.idx，[x,R)区间每个值的v改变L.v-x.v，每个节点d的懒标记和v的懒标记可以同时存在（乘法分配律），答案（sum）不做懒标记（没有必要）
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 #define int long long
5
6 const int maxn=3e5+10;
7 int a[maxn],cnt=1;
8
9 struct node{
10 int lson;
11 int rson;
12 int sum;
13 int w; //距离d在代码里为w
14 int v;
15 int wadd; //$add为懒标记
16 int vadd;
17 };
18
19 struct edge{
20 int idx;
21 int v;
22 };
23
24 struct question{
25 int op;
26 int x1;
27 int x2;
28 };
29
30 node tre[maxn*4];
31
32 bool cmp(edge a,edge b)
33 {
34 return a.idx<b.idx;
35 }
36
37 void pushup(int k)
38 {
39 tre[k].sum=tre[tre[k].lson].sum+tre[tre[k].rson].sum;
40 tre[k].v=tre[tre[k].lson].v+tre[tre[k].rson].v;
41 tre[k].w=tre[tre[k].lson].w+tre[tre[k].rson].w;
42 }
43
44 void pushdown(int k,int ln,int rn)
45 {
46 if (tre[k].vadd){ //下推v
47 if (!tre[k].lson) tre[k].lson=++cnt;
48 if (!tre[k].rson) tre[k].rson=++cnt;
49 tre[tre[k].lson].vadd+=tre[k].vadd;
50 tre[tre[k].rson].vadd+=tre[k].vadd;
51 tre[tre[k].lson].sum+=tre[tre[k].lson].w*tre[k].vadd;
52 tre[tre[k].rson].sum+=tre[tre[k].rson].w*tre[k].vadd;
53 tre[tre[k].lson].v+=tre[k].vadd*ln;
54 tre[tre[k].rson].v+=tre[k].vadd*rn;
55 tre[k].vadd=0;
56 }
57 if (tre[k].wadd){ //下推w
58 if (!tre[k].lson) tre[k].lson=++cnt;
59 if (!tre[k].rson) tre[k].rson=++cnt;
60 tre[tre[k].lson].wadd+=tre[k].wadd;
61 tre[tre[k].rson].wadd+=tre[k].wadd;
62 tre[tre[k].lson].sum+=tre[tre[k].lson].v*tre[k].wadd;
63 tre[tre[k].rson].sum+=tre[tre[k].rson].v*tre[k].wadd;
64 tre[tre[k].lson].w+=tre[k].wadd*ln;
65 tre[tre[k].rson].w+=tre[k].wadd*rn;
66 tre[k].wadd=0;
67 }
68 }
69
70 int find(int c,int t,int l,int r,int k)
71 {
72 if (l>=c&&r<=t){
73 return tre[k].sum;
74 }
75 int mid=(l+r)/2;
76 pushdown(k,mid-l+1,r-mid);
77 int ans=0;
78 if (mid>=c) ans+=find(c,t,l,mid,tre[k].lson);
79 if (mid<t) ans+=find(c,t,mid+1,r,tre[k].rson);
80 return ans;
81 }
82
83 void update(int c,int t,int l,int r,int k,int dcg,int vcg)
84 {
85 int mid=(l+r)/2;
86 if (!k) k=++cnt;
87 if (c<=l&&t>=r){
88 if (vcg){
89 tre[k].vadd+=vcg;
90 tre[k].v+=vcg*(r-l+1);
91 tre[k].sum+=tre[k].w*vcg;
92 }
93 if (dcg) {
94 tre[k].wadd+=dcg;
95 tre[k].w+=dcg*(r-l+1);
96 tre[k].sum+=tre[k].v*dcg;
97 }
98 return;
99 }
100 pushdown(k,mid-l+1,r-mid);
101 if (mid>=c) update(c,t,l,mid,tre[k].lson,dcg,vcg);
102 if (mid<t) update(c,t,mid+1,r,tre[k].rson,dcg,vcg);
103 pushup(k);
104 }
105
106 void build(int &k,int l,int r,int d,int v,int id)
107 {
108 if (!k) k=++cnt;
109 if (l==r){
110 tre[k].sum=v*d;
111 tre[k].v=v;
112 tre[k].w=d;
113 }
114 else{
115 int mid=(l+r)/2;
116 if (id<=mid) build(tre[k].lson,l,mid,d,v,id);
117 if (id>mid) build(tre[k].rson,mid+1,r,d,v,id);
118 pushup(k);
119 }
120 }
121
122 signed main()
123 {
124 ios::sync_with_stdio(false);
125 cin.tie(0);cout.tie(0);
126 int _=1;
127 while (_--){
128 int n,m,q;
129 cin>>n>>m>>q;
130 vector <edge> pre(n+10),las(n+10);
131 vector <edge> has(m);
132 for (int i=0;i<m;i++) cin>>has[i].idx;
133 for (int i=0;i<m;i++) cin>>has[i].v;
134 vector <question> sd;
135 for (int i=1;i<=q;i++){
136 int op,x,c;
137 cin>>op>>x>>c;
138 sd.push_back({op,x,c});
139 if (op==1) has.push_back({x,c});
140 }
141 sort(&has[0],&has[has.size()],cmp);
142 for (int i=0;i<(int)has.size();i++){ //创建链表
143 if (i) pre[has[i].idx].idx=has[i-1].idx,pre[has[i].idx].v=has[i-1].v;
144 if (i!=(int)has.size()-1) las[has[i].idx].idx=has[i+1].idx,las[has[i].idx].v=has[i+1].v;
145 }
146 int vpoint=0,dpoint=0;
147 for (int i=1;i<=n;i++){ //预处理
148 while (vpoint<(int)has.size()&&has[vpoint].idx<=i) vpoint++;
149 while (dpoint<(int)has.size()&&has[dpoint].idx<i) dpoint++;
150 int k=1;
151 build(k,1,n,has[dpoint].idx-i,has[vpoint-1].v,i);
152 }
153 vector <int> ans;
154 for (int i=q-1;i>=0;i--){
155 if (sd[i].op==1){ //链表删除节点+线段树区间修改
156 int idx=sd[i].x1,v=sd[i].x2;
157 pre[las[idx].idx].idx=pre[idx].idx;
158 las[pre[idx].idx].idx=las[idx].idx;
159 pre[las[idx].idx].v=pre[idx].v;
160 las[pre[idx].idx].v=las[idx].v;
161 int k=1;
162 update(idx,las[idx].idx-1,1,n,k,0,pre[idx].v-v);
163 k=1;
164 update(pre[idx].idx+1,idx,1,n,k,las[idx].idx-idx,0);
165 }
166 else{ //区间查询
167 int L=sd[i].x1,R=sd[i].x2;
168 ans.push_back(find(L,R,1,n,1));
169 }
170 }
171 while ((int)ans.size()){
172 cout<<ans.back()<<'\n';
173 ans.pop_back();
174 }
175 }
176 }
标签：idx,int,tre,Codeforces,long,cin,ans,921,Div From： https://www.cnblogs.com/Favelcpp/p/17993511