B：
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<double,int> pii; const int N = 1e6+5; const int M = 1e6+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();} return x * f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; int a[N]; struct Node{int L,r,maxx;}node[N << 2]; void Pushup(int idx){node[idx].maxx = max(node[idx << 1].maxx,node[idx << 1 | 1].maxx);} void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r,node[idx].maxx = 0; if(L == r) return ; int mid = (L + r) >> 1; build(L,mid,idx << 1); build(mid + 1,r,idx << 1 | 1); } int query(int x,int idx) { if(node[idx].L == node[idx].r) return node[idx].L; int mid = (node[idx].L + node[idx].r) >> 1; if(node[idx << 1].maxx >= x) return query(x,idx << 1); else return query(x,idx << 1 | 1); } void update(int x,int val,int idx) { if(node[idx].L == node[idx].r) { node[idx].maxx += val; return ; } int mid = (node[idx].L + node[idx].r) >> 1; if(mid >= x) update(x,val,idx << 1); else update(x,val,idx << 1 | 1); Pushup(idx); } set<int> S; map<int,int> mp; int main() { int ca;ca = read(); while(ca--) { int n,c;n = read(),c = read(); for(rg int i = 1;i <= n;++i) a[i] = read(); int num1 = 0,num2 = 0; build(1,n,1); for(rg int i = 1;i <= n;++i) { int pos = -1; if(node[1].maxx >= a[i]) pos = query(a[i],1); if(pos == -1) ++num1,update(num1,c - a[i],1); else update(pos,-a[i],1); } S.clear();mp.clear(); for(rg int i = 1;i <= n;++i) { auto ip = S.end(); if(S.size() == 0 || *(--ip) < a[i]) num2++,S.insert(c - a[i]),mp[c - a[i]]++; else { auto pos = S.lower_bound(a[i]); int tmp = *pos - a[i]; mp[*pos]--; mp[tmp]++; if(mp[*pos] == 0) S.erase(*pos); if(mp[tmp] == 1) S.insert(tmp); } } printf("%d %d ",num1,num2); } system("pause"); return 0; }
C：
细节有点多。
注意的是这里的字典是M组（带着各自的代价）。
然后再去查询矩阵里的字符串。并且这个字符串必定满足连贯的非子串的完整字符串（且必须只能左到右读，或者上到下来读）
那么就可以构造字典树来查询。因为这里保证了总字典长度<= 4e6
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<double,int> pii; const int N = 4e6+5; const int M = 1e6+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();} return x * f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; string a[1005]; int tree[N][30],sum[N],k = 0; void Insert(string s,int w) { int len = s.size(),p = 0; for(rg int i = 0;i < len;++i) { int c = s[i] - 'a'; if(!tree[p][c]) tree[p][c] = ++k; p = tree[p][c]; } sum[p] = w; } int query(string s) { int len = s.size(),p = 0; for(rg int i = 0;i < len;++i) { int c = s[i] - 'a'; if(!tree[p][c]) return 0; p = tree[p][c]; } return sum[p]; } int main() { ios :: sync_with_stdio(false); cin.tie(0),cout.tie(0); int ca;cin >> ca; while(ca--) { for(rg int i = 0;i <= k;++i) { sum[i] = 0; for(rg int j = 0;j < 30;++j) tree[i][j] = 0; } k = 0; int n,m,f = 0;cin >> n >> m; for(rg int i = 0;i < n;++i) cin >> a[i]; LL ans = 0; while(m--) { string s; int x; cin >> s >> x; Insert(s,x); } for(rg int i = 0;i < n;++i)//向右扫 { if(f) break; int L = -1; string s = ""; for(rg int j = 0;j < n;++j) { if(L == -1) { if(a[i][j] != '#' && (j == 0 || a[i][j - 1] == '#')) { L = j,s += a[i][j]; if(j == n - 1) { int x = query(s); if(x == 0) f = 1; else ans += x; L = -1,s = ""; } } } else { if(a[i][j] == '#') { int x = query(s); if(x == 0) f = 1; else ans += x; L = -1,s = ""; } else if(j == n - 1) { s += a[i][j]; int x = query(s); if(x == 0) f = 1; else ans += x; L = -1,s = ""; } else s += a[i][j]; } } } for(rg int j = 0;j < n;++j)//向下扫 { if(f) break; int L = -1; string s = ""; for(rg int i = 0;i < n;++i) { if(L == -1) { if(a[i][j] != '#' && (i == 0 || a[i - 1][j] == '#')) { L = i,s += a[i][j]; if(i == n - 1) { int x = query(s); if(x == 0) f = 1; else ans += x; L = -1,s = ""; } } } else { if(a[i][j] == '#') { int x = query(s); if(x == 0) f = 1; else ans += x; L = -1,s = ""; } else if(i == n - 1) { s += a[i][j]; int x = query(s); if(x == 0) f = 1; else ans += x; L = -1,s = ""; } else s += a[i][j]; } } } if(f) ans = -1; cout << ans << endl; } system("pause"); return 0; }
E:
仔细读懂题的话，就是i^2的前缀和 + 区间的前k大的和。
直接上主席树就行。
i * i写成了a[i] * a[i]调了N久（笨比一个）
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<double,int> pii; const int N = 1e5+5; const int M = 1e6+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();} return x * f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; int rt[N],top = 0; LL sum[N],a[N]; struct Node{int L,r;LL cnt,sum;}node[M * 20]; void Pushup(int idx) { int ls = node[idx].L,rs = node[idx].r; node[idx].sum = node[ls].sum + node[rs].sum; node[idx].cnt = node[ls].cnt + node[rs].cnt; } int build(int L,int r) { int idx = ++top; node[idx].cnt = node[idx].sum = 0; if(L == r) return idx; int mid = (L + r) >> 1; node[idx].L = build(L,mid); node[idx].r = build(mid + 1,r); return idx; } int Insert(int L,int r,int idx1,int x) { int idx2 = ++top; node[idx2] = node[idx1]; if(L == r) { node[idx2].cnt++; node[idx2].sum = node[idx2].cnt * L; return idx2; } int mid = (L + r) >> 1; if(mid >= x) node[idx2].L = Insert(L,mid,node[idx1].L,x); else node[idx2].r = Insert(mid + 1,r,node[idx1].r,x); Pushup(idx2); return idx2; } LL query(int x,int y,int L,int r,int k) { if((node[y].cnt - node[x].cnt) <= k) return node[y].sum - node[x].sum; if(L == r) return 1LL * L * k; int mid = (L + r) >> 1; int ls1 = node[x].L,rs1 = node[x].r; int ls2 = node[y].L,rs2 = node[y].r; LL rcnt = node[rs2].cnt - node[rs1].cnt; if(rcnt >= k) return query(rs1,rs2,mid + 1,r,k); else return node[rs2].sum - node[rs1].sum + query(ls1,ls2,L,mid,k - rcnt); } int main() { int ca;ca = read(); while(ca--) { top = 0; int n;n = read(); int mx = -1; for(rg int i = 1;i <= n;++i) a[i] = read(),mx = max(mx,(int)a[i]); for(rg int i = 1;i <= n;++i) sum[i] = sum[i - 1] + 1LL * i * i; rt[0] = build(1,mx); for(rg int i = 1;i <= n;++i) rt[i] = Insert(1,mx,rt[i - 1],a[i]); int q;q = read(); while(q--) { int L,r,k;L = read(),r = read(),k = read(); int m = r - L + 1; LL ans = sum[m]; ans += query(rt[L - 1],rt[r],1,mx,k); printf("%lld ",ans); } } system("pause"); return 0; }