$$\LARGE{\color{Orange}{\mathbf{Note-各种题目收录} } }$$
维护数组-周赛C
写一个支持:
1. 给数组中的一个数加上一个数
2.给定 $p$ 以及固定参数 $a$,$b$ ,输出: $\displaystyle{\sum_{i = 1}^{p - 1}\min(d_i,b)+\sum_{i = p + k}^n\min(d_i,a)}$
两个操作的数据结构.
唠嗑:这题树状数组是标准答案,线段树是万能答案(因为只要将单点修改改成区间修改就要线段树来操作)
更新: splay 也是万能答案(就是容易写错~~)
(性质). 因为我们可以发现:
(0). 可以分别维护两个树状数组 $B,A$ 来求 $\min(d_i,b)$ 与 $\min(d_i,a)$ 的和
(1). 一个数在树状数组 $B$ 最多加到 $b$ ,在树状数组 $A$ 最多加到 $a$ ,再多加就影响我们维护的前缀和了
(2). 后缀和可以用前缀和来处理,这一点体现在代码里
所以插入前,先判断要加到多少,如果加完后超出限制($a,b$),则减少加数
使其最终的值只能在限制的值($a,b$)或者小于它们
树状数组 $O(q\log n)$
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 200010;
int tr1[N],tr2[N],n,k,q,a,b;
void insert(int *tr,int u,int x)
{
for(int i = u;i <= n;i += lowbit(i))
tr[i] += x;
}
int sum(int *tr,int u)
{
int res = 0;
for(int i = u;i;i -= lowbit(i))
res += tr[i];
return res;
}
int main()
{
fastio();
cin >> n >> k >> a >> b >> q;
while(q -- )
{
int op,x,y;
cin >> op;
if(op == 1)
{
int t,val;
cin >> x >> y;
val = sum(tr1,x) - sum(tr1,x - 1);
if(b <= val) t = 0;
else t = min(b - val,y);
insert(tr1,x,t);
x = n + 1 - x;
val = sum(tr2,x) - sum(tr2,x - 1);
if(a <= val) t = 0;
else t = min(a - val,y);
insert(tr2,x,t);
}
else cin >> x,cout << sum(tr1,x - 1) + sum(tr2,n + 1 - (x + k)) << endl;
}
return 0;
}
线段树 $O(q\log n)$
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 200010;
struct Node
{
int l,r;
int v,s1,s2;
}tr[N << 2];
int k,a,b;
void pushup(int x)
{
tr[x].s1 = tr[x << 1].s1 + tr[x << 1 | 1].s1;
tr[x].s2 = tr[x << 1].s2 + tr[x << 1 | 1].s2;
}
void build(int u,int l,int r)
{
tr[u] = {l,r};
if(l == r)
{
tr[u].s1 = min(b,0);
tr[u].s2 = min(a,0);
}
else
{
int mid = l + r >> 1;
if(l <= mid) build(u << 1,l,mid);
if(r > mid) build(u << 1 | 1,mid + 1,r);
pushup(u);
}
}
void change(int u,int x,int c)
{
if(tr[u].l == x && tr[u].r == x)
{
tr[u].v += c;
tr[u].s1 = min(b,tr[u].v);
tr[u].s2 = min(a,tr[u].v);
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
change(u << 1 | (x > mid),x,c);
pushup(u);
}
}
int ask(int u,int l,int r,int type)
{
if(tr[u].l >= l && tr[u].r <= r)
if(type == 0) return tr[u].s1;
else return tr[u].s2;
else
{
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid) res += ask(u << 1,l,r,type);
if(r > mid) res += ask(u << 1 | 1,l,r,type);
return res;
}
}
int main()
{
fastio();
int n,q;cin >> n >> k >> a >> b >> q;
build(1,1,n);
while(q -- )
{
int op,x,y;
cin >> op;
if(op == 1)
{
cin >> x >> y;
change(1,x,y);
}
else cin >> x,cout << ask(1,1,x - 1,0) + ask(1,x + k,n,1) << endl;
}
return 0;
}
splay
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 200010;
int n,q,k,a,b;
struct Node
{
int s[2],v,p,sa,sb,sz;
void init(int _v,int _p)
{
v = _v,p = _p;
sz = 1;
}
}tr[N];
int root,idx;
void pushup(int u)
{
tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + 1;
tr[u].sa = tr[tr[u].s[0]].sa + tr[tr[u].s[1]].sa + min(tr[u].v,a);// key
tr[u].sb = tr[tr[u].s[0]].sb + tr[tr[u].s[1]].sb + min(tr[u].v,b);// key
}
void rotate(int x)
{
int y = tr[x].p,z = tr[y].p;
int k = (x == tr[y].s[1]);
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y),pushup(x);
}
void splay(int x,int k)
{
while(tr[x].p != k)
{
int y = tr[x].p,z = tr[y].p;
if(z != k)
{
if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root = x;
}
int build(int l,int r,int p)
{
int mid = l + r >> 1;
int u = ++ idx;
tr[u].init(0,p);
if(l < mid) tr[u].s[0] = build(l,mid - 1,u);
if(r > mid) tr[u].s[1] = build(mid + 1,r,u);
pushup(u);
return u;
}
int kth(int k)
{
int u = root;
while(u)
{
if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
else if(tr[tr[u].s[0]].sz + 1 == k) return u;
else k -= tr[tr[u].s[0]].sz + 1,u = tr[u].s[1];
}
return -1;
}
int main()
{
fastio();
cin >> n >> k >> a >> b >> q;
root = build(0,n + 1,0);
while(q -- )
{
int op;cin >> op;
if(op == 1)
{
int x,y,L,R;
cin >> x >> y;
L = kth(x),R = kth(x + 2);
splay(L,0),splay(R,L);
auto &node = tr[tr[R].s[0]];
node.v += y;
node.sa = min(node.v,a);
node.sb = min(node.v,b);
pushup(R),pushup(L);
}
else
{
int p,res,L,R;
cin >> p;res = 0;
L = kth(1),R = kth(p + 1);
splay(L,0),splay(R,L);
res += tr[tr[R].s[0]].sb;
L = kth(p + k),R = kth(n + 2);
splay(L,0),splay(R,L);
res += tr[tr[R].s[0]].sa;
cout << res << endl;
}
}
return 0;
}