OTZ做出题目的神犇。。断断续续改完了在这里存一下思路吧
A题：第K大区间
题意：
定义一个区间的值为其众数出现的次数。
现给出n个数，求将所有区间的值排序后，第K大的值为多少。
分析：
二分答案mid，任务就是判定有多少个区间的众数≥mid。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n, A[maxn], c[maxn], cnt[maxn], mx, tmp[maxn];
ll k;
void Add(int x){
cnt[c[x]] --;
c[x] ++;
cnt[c[x]] ++;
mx = max(mx, c[x]);
}
void Del(int x){
cnt[c[x]] --;
c[x] --;
cnt[c[x]] ++;
while(!cnt[mx])mx --;
}
int check(int x){
ll ans = 0, l = 1; mx = 0;
memset(cnt, 0, sizeof cnt);
memset(c, 0, sizeof c);
cnt[0] = n;
for(int i = 1; i <= n; i ++){
Add(A[i]);
while(true){
Del(A[l]);
if(mx < x) {Add(A[l]); break;}
l ++;
}
if(mx >= x) ans += l;
}
return ans >= k;
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++){
scanf("%d", &A[i]);
tmp[i] = A[i];
}
sort(tmp+1, tmp+1+n);
int p = unique(tmp+1, tmp+1+n) - tmp - 1;
for(int i = 1; i <= n; i ++)
A[i] = lower_bound(tmp+1, tmp+1+p, A[i]) - tmp;
int l = 1, r = n+1;
while(l < r){
int mid = l + (r - l + 1) / 2;
if(check(mid))l = mid;
else r = mid - 1;
}
printf("%d\n", l);
return 0;
}
B题戳这里
C题：逛街
分析：
对于喜欢的店的个数一定要大于等于k，这个可以用一个堆来贪心，维护堆中的元素等于k个，对于其他的离散化一下扔进线段树(splay也不介意，但是好像会t)
然后在线段树上二分
注意val有负值a。。然后不能加a
#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long ll;
int n, T, k, root, smz;
int A[maxn], B[maxn], C[maxn];
long long sum[maxn];
priority_queue<pair<ll, int> > Q;
int b[maxn];
struct Hash{
int id, p;
ll val;
bool operator<(const Hash& k)const{return val < k.val;}
}h[maxn];
bool cmp(const Hash& a, const Hash& b){return a.p < b.p;}
struct Node{
int l, r, size; ll sum;
}t[maxn << 2];
#define lc id<<1
#define rc id<<1|1
void build(int id, int l, int r){
t[id].l = l, t[id].r = r;
if(l == r)return;
int mid = l+r >> 1;
build(lc, l, mid);
build(rc, mid+1, r);
}
void pushup(int id){
t[id].sum = t[lc].sum + t[rc].sum;
t[id].size = t[lc].size + t[rc].size;
}
void update(int id, int pos, ll val){
if(val < 0)return;
if(t[id].l == t[id].r){
t[id].sum = val;
t[id].size ++;
return;
}
int mid = t[id].l + t[id].r >> 1;
if(pos <= mid)update(lc, pos, val);
else update(rc, pos, val);
pushup(id);
}
int ask(int id, ll T){
if(t[id].l == t[id].r)return min(t[id].size, (int)(T >= t[id].sum));
if(T >= t[lc].sum)return t[lc].size + ask(rc, T - t[lc].sum);
return ask(lc, T);
}
int vis[maxn];
int main(){
scanf("%d%d%d", &n, &T, &k);
for(int i = 1; i <= n; i ++)scanf("%d", &A[i]);
for(int i = 1; i <= n; i ++)scanf("%d", &B[i]), h[i].val = B[i], h[i].p = i;
for(int i = 1; i <= n; i ++)scanf("%d", &C[i]);
sort(h+1, h+1+n);
for(int i = 1; i <= n; i ++)
h[i].id = i;
sort(h+1, h+1+n, cmp);
for(int i = 1; i <= n; i ++)b[i] = h[i].id;
build(1, 1, n);
int ans = 0;
ll Sum = 0;
for(int i = 1; i <= n; i ++){
if(C[i]){
if(Q.size() < k)Q.push(make_pair(B[i], i)), Sum += B[i];
else if(!Q.empty() && (Q.size() == k && B[i] < Q.top().first)){
ll t = Q.top().first;
int t1 = Q.top().second;Q.pop();
Q.push(make_pair(B[i], i));Sum = Sum - t + B[i];
update(1, b[t1], t);
}else update(1, b[i], B[i]);
}
else update(1, b[i], B[i]);
if(Q.size() >= k && Sum + A[i] <= T)ans = max(ans, k + ask(1, T - Sum - A[i]));
}
if(ans < k)puts("-1");
else printf("%d\n", ans);
return 0;
}
D题：Rikka with Sequences
题目大意：给定一个序列，有更改操作，每次查询一段区间的历史区间和最小值。
n, m ≤ 10^5, Ai ≤ 10^9
分析：
这个在线好难做a。所以就要离线la。所以就要用KD-tree啦。(QAQ)
对于每一个操作我们可以计算它对询问的贡献。把一个询问看成二维平面上的一个点(l, r)，每一次操作都是将(pos, pos)左上角(l <= pos, r >= pos)的询问更改一下，通过打标记来实现历史最小值的询问。时光倒流，如果是每次给一个位置添加数字，询问历史最小值是个经典问题la
一定不要忘记pushdown。。。一定不要忘记mn[i]和mx[i]
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long ll;
const int inf = 0x7fffffff;
int n, m, dfs_clock, D;
//----------------------KD-tree--------------------------//
struct Node{
int l, r, mn[2], mx[2], d[2], id;
ll sum, add, ans, Minadd;
int& operator[](const int& k){return d[k];}
bool operator<(Node k)const{return d[D] < k[D];}
Node(int x = 0, int y = 0, int i = 0, ll s = 0){
sum = ans = s, id = i;
mn[0] = mx[0] = d[0] = x;
mn[1] = mx[1] = d[1] = y;
l = r = add = Minadd = 0;
}
}t[maxn], dfn[maxn], P;
int tot, root;
void update(int o){
for(int i = 0; i < 2; i ++){
t[o].mn[i] = t[o].mx[i] = t[o][i];
if(t[o].l){
t[o].mn[i] = min(t[o].mn[i], t[t[o].l].mn[i]);
t[o].mx[i] = max(t[o].mx[i], t[t[o].l].mx[i]);
}
if(t[o].r){
t[o].mn[i] = min(t[o].mn[i], t[t[o].r].mn[i]);
t[o].mx[i] = max(t[o].mx[i], t[t[o].r].mx[i]);
}
}
}
int Newnode(){
t[++ tot] = P;
return tot;
}
inline void Down1(int o, ll val){
if(!o)return;
t[o].ans = min(t[o].ans, t[o].sum + val);
t[o].Minadd = min(t[o].Minadd, t[o].add + val);
}
inline void Down2(int o, ll val){
if(!o)return;
t[o].ans = min(t[o].ans, t[o].sum += val);
t[o].Minadd = min(t[o].Minadd, t[o].add += val);
}
inline void pushdown(int o){
if(t[o].Minadd){
Down1(t[o].l, t[o].Minadd), Down1(t[o].r, t[o].Minadd);
t[o].Minadd = 0;
}
if(t[o].add){
Down2(t[o].l, t[o].add), Down2(t[o].r, t[o].add);
t[o].add = 0;
}
}
void Modify(int o, int pos, ll val){
pushdown(o);
if(t[o].mx[0] <= pos && t[o].mn[1] >= pos) {Down2(o, val); return;}
if(t[o][0] <= pos && t[o][1] >= pos)t[o].sum += val, t[o].ans = min(t[o].ans, t[o].sum);
if(t[o].l && t[t[o].l].mn[0] <= pos && t[t[o].l].mx[1] >= pos)Modify(t[o].l, pos, val);
if(t[o].r && t[t[o].r].mn[0] <= pos && t[t[o].r].mx[1] >= pos)Modify(t[o].r, pos, val);
}
void Insert(int o, int type){
pushdown(o), D = type;
if(P < t[o]){
if(t[o].l)Insert(t[o].l, type^1);
else t[o].l = Newnode();
}
else{
if(t[o].r)Insert(t[o].r, type^1);
else t[o].r = Newnode();
}
update(o);
}
ll ans[maxn];
void dfs(int o){
pushdown(o);
dfn[++ dfs_clock] = t[o];
ans[t[o].id] = t[o].ans;
if(t[o].l)dfs(t[o].l);
if(t[o].r)dfs(t[o].r);
}
int build(int l, int r, int type){
if(l > r)return 0; D = type;
int mid = l + r >> 1;
nth_element(dfn+l, dfn+mid, dfn+r+1);
t[mid] = dfn[mid];
t[mid].l = build(l, mid-1, type^1);
t[mid].r = build(mid+1, r, type^1);
update(mid); return mid;
}
//----------------------query---------------------------//
int tp[maxn], l[maxn], r[maxn];
//----------------------BIT-----------------------------//
ll A[maxn], Bit[maxn];
#define lowbit(i) i&(~i+1)
void add(int pos, ll val){
for(int i = pos; i <= n; i += lowbit(i))
Bit[i] += val;
}
ll ask(int pos){
if(!pos)return 0;ll ret = 0;
for(int i = pos; i; i -= lowbit(i))
ret += Bit[i];
return ret;
}
//----------------------solve---------------------------//
int main(){
root = Newnode();
t[root].mn[0] = t[root].mn[1] = inf;
t[root].mx[0] = t[root].mx[1] = -inf;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
scanf("%lld", &A[i]), add(i, A[i]);
for(int i = 1; i <= m; i ++){
scanf("%d%d%d", &tp[i], &l[i], &r[i]);
if(tp[i] == 1){
r[i] -= A[l[i]];//增量
A[l[i]] += r[i];
add(l[i], r[i]);
}
}
int Buf = 2000;
for(int i = m; i >= 1; i --){
if(tp[i] == 1){
add(l[i], -r[i]);
Modify(root, l[i], -r[i]);
}
else{
P = Node(l[i], r[i], i, ask(r[i]) - ask(l[i]-1));
Insert(root, 0);
}
if(i % Buf == 0)dfs_clock = 0, dfs(root), root = build(1, dfs_clock, 0);
}
dfs_clock = 0, dfs(root);
for(int i = 1; i <= m; i ++)
if(tp[i] == 2)printf("%lld\n", ans[i]);
return 0;
}
E题：小Z的Tire
广义后缀自动机。倍增找到位置输出parent树中子树节点个数
#include <bits/stdc++.h>
#define maxn 2000010
using namespace std;
struct Node{int len, link, nxt[26];}st[maxn];
int root, size, last;
int s[maxn];
void init(){
root = size = last = 0;
st[root].len = 0;
st[root].link = -1;
}
void Extend(char ch){
int c = ch - 'a', p = last, q = st[p].nxt[c];
if(q){
if(st[q].len == st[p].len + 1)
last = q;
else{
int clone = ++ size;
st[clone] = st[q];
st[clone].len = st[p].len + 1;
for(; ~p && st[p].nxt[c] == q; p = st[p].link)
st[p].nxt[c] = clone;
st[q].link = clone;
last = clone;
}
}
else{
int cur = ++ size;
st[cur].len = st[p].len + 1;
for(; ~p && !st[p].nxt[c]; p = st[p].link)
st[p].nxt[c] = cur;
if(p == -1)
st[cur].link = root;
else{
q = st[p].nxt[c];
if(st[q].len == st[p].len + 1)
st[cur].link = q;
else{
int clone = ++ size;
st[clone] = st[q];
st[clone].len = st[p].len + 1;
for(; ~p && st[p].nxt[c] == q; p = st[p].link)
st[p].nxt[c] = clone;
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
s[last] = 1;
}
int n;
char c[maxn];
int anc[maxn][22];
int t[maxn], w[maxn];
void pre_anc(){
for(int i = 1; i <= size; i ++)w[st[i].len] ++;
for(int i = 1; i <= size; i ++)w[i] += w[i-1];
for(int i = 1; i <= size; i ++)t[w[st[i].len] --] = i;
for(int i = size; i >= 1; i --)s[st[t[i]].link] += s[t[i]];
memset(anc, -1, sizeof anc);
for(int i = 1; i <= size; i ++)
anc[i][0] = st[i].link;
for(int j = 1; 1 << j <= size; j ++){
for(int i = 1; i <= size; i ++){
int a = anc[i][j-1];
if(~a)anc[i][j] = anc[a][j-1];
}
}
}
vector<int>V[100010];
int ask_pos(int r, int len){
int now = r;
for(int i = 21; i >= 0; i --){
int t = anc[now][i];
if(t == -1)continue;
if(st[t].len >= len)now = t;
}
return now;
}
int main(){
init();
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%s", c+1);
int N = strlen(c+1);
last = root;
for(int j = 1; j <= N; j ++){
Extend(c[j]);
V[i].push_back(last);
}
}
pre_anc();
int m, u, v, d;
scanf("%d", &m);
for(int i = 1; i <= m; i ++){
scanf("%d%d%d", &u, &v, &d);
printf("%d\n", s[ask_pos(V[u][d-1], d-v+1)]);
}
return 0;
}
