\(BIT\)
大家都会。
//可单点修改区间查询的BIT
//BIT<N> tree; 定义一个大小为 N 的BIT
//modify(x, v) a[x] += v
//query(x) -> sum(1, x)的值
//query(x, y) -> sum(x, y)的值
template<int SIZ>
struct BIT{
#define inl inline
#define I int
I c[SIZ];
inl I lb(I x){return x & (-x);}
inl void modify(I x, I v){for(; x < SIZ; x+=lb(x)) c[x] += v;}
inl I query(I x){int cur = 0; while(x){cur += c[x], x -= lb(x);} return cur;}
inl I query(I x, I y){return query(y) - query(x-1);}
};
//可区间修改单点查询的BIT
//BIT<N> tree; 定义一个大小为 N 的BIT
//modify(l, r, v) a[l~r] += v
//query(x) -> a[x] 的值
template<int SIZ>
struct BIT{
#define inl inline
#define I int
I c[SIZ];
inl I lb(I x){return x & (-x);}
inl void modify(I x, I v){for(; x < SIZ; x+=lb(x)) c[x] += v;}
inl void modify(I l, I r, I v){modify(l, v), modify(r+1, -v);}
inl I query(I x){int cur = 0; while(x){cur += c[x], x -= lb(x);} return cur;}
};
线段树
大家都会。
// Author: __ODT__
// web: https://www.luogu.com.cn/problem/SP1716
// SP1716 GSS3 - Can you answer these queries III
// Accepted
/*
题意：
n 个数，q 次操作
操作 0 x y 把 a[x] 修改为 y
操作 1 l r 询问区间 [l,r] 的最大子段和
*/
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5;
const int inf = 0x3f3f3f3f;
#define I int
struct node{
I all, maxmid, l, r;
friend bool operator == (node x, node y){
return x.all == y.all && x.maxmid == y.maxmid && x.l == y.l && x.r == y.r;
}
};
node nones = (node){-inf, -inf, -inf, -inf};
void merge(node &mg, node x, node y){
if(x == nones) mg = y;
if(y == nones) mg = x;
if(x == nones || y == nones) return;
mg.all = x.all + y.all;
mg.maxmid = max(max(x.maxmid, y.maxmid), x.r+y.l);
mg.l = max(x.l, x.all+y.l);
mg.r = max(y.r, y.all+x.r);
}
void init(node &x, int val){x.all = x.maxmid = x.l = x.r = val;}
int n, a[N];
struct segmenttree
{
node t[N<<2];
#define lc ((k)<<(1))
#define rc ((k)<<(1)|(1))
#define mid ((l)+(r)>>(1))
void pushup(int k){merge(t[k], t[lc], t[rc]);}
void build(int k = 1, int l = 1, int r = n){
if(l == r){init(t[k], a[l]);return;}
build(lc, l, mid), build(rc, mid+1, r);
pushup(k);
}
void modify(int x, int y, int k = 1, int l = 1, int r = n){
if(l == r){init(t[k], y); return;}
if(x <= mid) modify(x, y, lc, l, mid);
else modify(x, y, rc, mid+1, r);
pushup(k);
}
node query(int x, int y, int k = 1, int l = 1, int r = n){
if(x > r || y < l) return nones;
if(l >= x && r <= y) return t[k];
node cur; merge(cur, query(x, y, lc, l, mid), query(x, y, rc, mid+1, r));
return cur;
}
}sgt;
inline I read(){
static I bo, x; bo = x = 0; static char c; c = getchar();
while(c < '0' || c > '9'){if(c == '-')bo = 1; c = getchar();}
while(c >= '0' && c <= '9') {x = (x<<3) + (x<<1) + c - '0'; c = getchar();}
return bo ? -x : x;
}
inline void out(I x, bool bo = true){
if(x < 0) putchar('-'), x = -x;
if(x == 0){if(bo)putchar('0'); return;}
out(x/10, false), putchar('0' + x%10);
}
int main(){
n = read();
for(int i = 1; i <= n; i ++) a[i] = read();
sgt.build();
int q = read();
for(int i = 1; i <= q; i ++){
int opt = read(), l = read(), r = read();
if(opt) out((sgt.query(l, r)).maxmid), puts("");
else sgt.modify(l, r);
}
return 0;
}
\(RMQ\)
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,a[1111111];
int f[1111111][24];
int lg[1111111];
int main()
{
memset(f,-1,sizeof(f));
n=read();
m=read();
for(int i=1; i<=n; i++)
f[i][0]=read();
for(int j=1; j<=23; j++)
{
for(int i=1; i+(1<<j)-1<=n; i++)
{
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
for(int i=1; i<=m; i++)
{
int l=read(),r=read();
int c=log2(r-l+1);
printf("%d\n",max(f[l][c],f[r-(1<<c)+1][c]));
}
}
习题
P5848 [IOI2005]mou
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
using namespace std;
typedef int ll;
struct node{
ll sum, ls;
int val, lc, rc;
}t[5500005];
int cnt = 1, n;
void push_up(int k){
t[k].sum = t[t[k].lc].sum + t[t[k].rc].sum;
t[k].ls = max(t[t[k].lc].ls, t[t[k].rc].ls + t[t[k].lc].sum);
return;
}
void Setv(int k, int v, int l, int r){
assert(l <= r);
t[k].sum = (ll)(r - l + 1) * (t[k].val = v);
t[k].ls = max(0, t[k].sum);
t[k].lc = t[k].rc = 0;
}
void push_down(int k, int l, int r){
int mid = l + r >> 1;
t[k].lc = ++cnt;
t[k].rc = ++cnt;
Setv(t[k].lc, t[k].val, l, mid);
Setv(t[k].rc, t[k].val, mid+1, r);
return;
}
void add(int k, int l, int r, int x, int y, int z){
int mid = l + r >> 1;
if(l >= x and r <= y){
Setv(k, z, l, r);
return;
}
if(t[k].lc == t[k].rc and t[k].lc == 0) push_down(k, l, r);
if(x <= mid) add(t[k].lc, l, mid, x, y, z);
if(y > mid) add(t[k].rc, mid+1, r, x, y, z);
push_up(k);
}
int ask(int k, int l, int r, ll high){
if(high >= t[k].ls) return r;
if(t[k].lc == t[k].rc and t[k].lc == 0) return l + (high / t[k].val) - 1;
int mid = l + r >> 1;
return high >= t[t[k].lc].ls ? ask(t[k].rc, mid + 1, r, high - t[t[k].lc].sum) : ask(t[k].lc, l, mid, high);
}
int main(){
cin >> n; char s;
for(int x, y, z; cin >> s and s != 'E';){
if(s == 'I'){cin >> x >> y >> z; add(1, 1, n, x, y, z);}
else {cin >> x;cout << ask(1, 1, n, x) << '\n';}
}
return 0;
}
UVA11992 Fast Matrix Operations
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
struct node{
int tag1, tag2, _max, _min;
int sum;
void Tag1(int x, int L, int R){
sum = x * (R - L + 1);
_max = _min = tag1 = x;
tag2 = 0;
return;
}
void Tag2(int x, int L, int R){
sum += x * (R - L + 1);
_max += x, _min += x;
tag2 += x;
return;
}
};
node merge(node x, node y){
node k = {0,0, 0,0, 0};
k.sum = x.sum + y.sum;
k._max = max(x._max, y._max);
k._min = min(x._min, y._min);
return k;
}
struct Segment_Tree{
node tree[N<<2];
void build(int k, int l, int r){
tree[k] = {0,0, 0,0, 0};
if(l == r){return;}
int mid = l + r >> 1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
}
void push_down(int k, int l, int r){
int mid = l + r >> 1;
if(tree[k].tag1){
tree[k<<1].Tag1(tree[k].tag1, l, mid);
tree[k<<1|1].Tag1(tree[k].tag1, mid+1, r);
tree[k].tag1 = 0;
}
if(tree[k].tag2){
tree[k<<1].Tag2(tree[k].tag2, l, mid);
tree[k<<1|1].Tag2(tree[k].tag2, mid+1, r);
tree[k].tag2 = 0;
}
return;
}
void add(int k, int l, int r, int x, int y, int v, int opt){
if(l > y or r < x) return;
if(l >= x and r <= y){
if(opt == 1) tree[k].Tag1(v, l, r);
else tree[k].Tag2(v, l, r);
return;
}
push_down(k, l, r);
int mid = l + r >> 1;
if(x <= mid) add(k<<1, l, mid, x, y, v, opt);
if(y > mid) add(k<<1|1, mid + 1, r, x, y, v, opt);
tree[k] = merge(tree[k<<1], tree[k<<1|1]);
return;
}
node ask(int k, int l, int r, int x, int y){
if(l > y or r < x) return (node){0,0, -0x3f3f3f3f,0x3f3f3f3f, 0};
if(l >= x and r <= y) return tree[k];
push_down(k, l, r);
int mid = l + r >> 1;
return merge(ask(k<<1, l, mid, x, y), ask(k<<1|1, mid+1, r, x, y));
}
}Segment_tree[21];
int main(){
int r, c, m;
while(scanf("%d %d %d", &r, &c, &m) != EOF){
_for(i, 1, r) Segment_tree[i].build(1, 1, c);
_for(OPT, 1, m){
int opt, X1, X2, Y1, Y2, v;
scanf("%d%d%d%d%d", &opt, &X1, &Y1, &X2, &Y2);
if(opt == 1){
scanf("%d", &v);
_for(i, X1, X2)
Segment_tree[i].add(1, 1, c, Y1, Y2, v, 2);
}
if(opt == 2){
scanf("%d", &v);
_for(i, X1, X2)
Segment_tree[i].add(1, 1, c, Y1, Y2, v, 1);
}
if(opt == 3){
node Ans = (node){0,0, -0x3f3f3f3f,0x3f3f3f3f, 0};
_for(i, X1, X2)
Ans = merge(Ans, Segment_tree[i].ask(1, 1, c, Y1, Y2));
printf("%d %d %d\n", Ans.sum, Ans._min, Ans._max);
}
}
}
return 0;
}
UVA12419 Heap Manager
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int N = 1e6;
struct node{
int ch[2], tag, lz, rz, midz;
};
struct Segment_Tree{
#define lc t[k].ch[0]
#define rc t[k].ch[1]
int cnt = 1;
node t[N<<2];
inline void push_up(int k, int l, int r){
int mid = l + r >> 1;
t[k].lz = (mid - l + 1 == t[lc].lz ? t[lc].lz + t[rc].lz : t[lc].lz);
t[k].rz = ( r - mid == t[rc].rz ? t[rc].rz + t[lc].rz : t[rc].rz);
t[k].midz = max(max(t[lc].midz, t[rc].midz), t[lc].rz + t[rc].lz);
}
inline void setv(int k, int l, int r, int co){
t[k].tag = co;
t[k].lz = t[k].rz = t[k].midz = (co == 1 ? r - l + 1 : 0);
}
inline void push_down(int k, int l, int r){
if(!lc) lc = ++cnt;
if(!rc) rc = ++cnt;
if(t[k].tag == 0)return;
int mid = l + r >> 1;
setv(lc, l, mid, t[k].tag);
setv(rc, mid+1, r, t[k].tag);
t[k].tag = 0;
}
inline void add(int k, int l, int r, int x, int y, int co){
if(r < x or l > y) return;
if(l >= x and r <= y){
setv(k, l, r, co);
return;
}
int mid = l + r >> 1;
push_down(k, l, r);
if(x <= mid) add(lc, l, mid, x, y, co);
if(y > mid) add(rc, mid+1, r, x, y, co);
push_up(k, l, r);
}
inline int ask(int k, int l, int r, int length){
if(t[k].lz >= length) return l;
push_down(k, l, r);
int mid = l + r >> 1;
if(t[lc].midz >= length) return ask(lc, l, mid, length);
if(t[lc].rz + t[rc].lz >= length) return mid - t[lc].rz + 1;
return ask(rc, mid+1, r, length);
}
}Segment_Trees;
struct outevent{
int t, l, r;
bool operator < (const outevent &rhs)const{
return t > rhs.t;
}
};
priority_queue<outevent> QQ;
struct event{
int len, t, id;
};
queue<event> q;
int n, b, pcnt, m, p;
void Add(int Tim, const event &x){
int wh = Segment_Trees.ask(1, 1, n, x.len);
Segment_Trees.add(1, 1, n, wh, wh + x.len - 1, 2);
QQ.push(outevent{x.t + Tim, wh, wh + x.len - 1});
if(b) printf("%d %d %d\n", Tim, x.id, wh - 1);
}
int main(){
while(cin >> n >> b){
int t, ans;
ans = t = 0;
pcnt = 0;
Segment_Trees.add(1, 1, n, 1, n, 1);
for(int i = 1; ; i ++){
cin >> t >> m >> p;
if(t == 0 and m == 0 and p == 0) t = 0x3f3f3f3f;
while(!QQ.empty() and QQ.top().t <= t){
int T = QQ.top().t;
while(!QQ.empty() and QQ.top().t == T){
const outevent& x = QQ.top();
ans = x.t;
Segment_Trees.add(1, 1, n, x.l, x.r, 1);
QQ.pop();
}
while(!q.empty() and q.front().len <= Segment_Trees.t[1].midz){
Add(T, q.front());
q.pop();
}
}
if(t == 0x3f3f3f3f)break;
if(m <= Segment_Trees.t[1].midz)Add(t, event{m, p, i});
else q.push(event{m, p, i}), pcnt++;
}
printf("%d\n%d\n\n", ans, pcnt);
}
return 0;
}
UVA1232 SKYLINE
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 11;
struct node{
int h1, h2, tag;
};
struct Segment_Tree{
node t[N<<2];
void push_up(int x){
t[x].h1 = min(t[x<<1].h1, t[x<<1|1].h1);
t[x].h2 = max(t[x<<1].h2, t[x<<1|1].h2);
}
void push_down(int k){
if(t[k].tag == 0) return;
t[k<<1].h1 = t[k<<1|1].h1 = t[k].tag;
t[k<<1].h2 = t[k<<1|1].h2 = t[k].tag;
t[k<<1].tag = t[k<<1|1].tag = t[k].tag;
t[k].tag = 0;
}
int ask(int k, int l, int r, int x, int y, int v){
if(t[k].h1 > v) return 0;
if(l >= x and r <= y){
if(t[k].h2 <= v){
t[k].h1 = t[k].tag = t[k].h2 = v;
return r - l + 1;
}
}
push_down(k);
int mid = l + r >> 1, ans = 0;
if(x <= mid) ans += ask(k<<1, l, mid, x, y, v);
if(y > mid) ans += ask(k<<1|1, mid+1, r, x, y, v);
push_up(k);
return ans;
}
}segment_tree;
int main(){
int T, n;
cin >> T;
while(T--){
memset(segment_tree.t, 0, sizeof segment_tree.t);
cin >> n;
int Ans = 0;
for(int i = 1; i <= n; i ++) {
static int x, y, v; cin >> x >> y >> v;
y--;
Ans += segment_tree.ask(1, 1, N - 11, x, y, v);
}
cout << Ans << endl;
}
return 0;
}
UVA11525 Permutation
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5;
int T, n;
struct Segment_Tree{
int sum[N<<2];
void push_up(int x) {sum[x] = sum[x<<1] + sum[x<<1|1];}
int kth(int k, int l, int r, int kths){
if(l == r) { sum[k] = 0; return l; }
int mid = l + r >> 1, ans;
if(sum[k<<1] >= kths) ans = kth(k<<1, l, mid, kths);
else ans = kth(k<<1|1, mid+1, r, kths - sum[k<<1]);
push_up(k); return ans;
}
void build(int k, int l, int r){
if(l == r){sum[k] = 1;return;}
int mid = l + r >> 1;
build(k<<1, l, mid), build(k<<1|1, mid+1, r);
push_up(k);
}
}Segment_Trees;
int main(){
scanf("%d", &T);
while(T--){
scanf("%d", &n);
Segment_Trees.build(1, 1, n);
for(int i = 1; i <= n; i ++){
static int x; scanf("%d", &x);
printf("%d", Segment_Trees.kth(1, 1, n, x + 1));
if(i < n) putchar(' ');
}
puts("");
}
}
UVA1455 Kingdom
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
struct node{
int sum, tag;
};
struct Segment_Tree{
node t[N<<2];
#define lc (k<<(1))
#define rc ((k<<(1))|(1))
void push_up(int k){t[k].sum = t[lc].sum + t[rc].sum;}
void push_down(int k, int l, int r){
if(t[k].tag == 0)return;
int mid = l + r >> 1;
t[lc].sum += t[k].tag * (mid - l + 1);
t[rc].sum += t[k].tag * (r - mid);
t[lc].tag += t[k].tag;
t[rc].tag += t[k].tag;
t[k].tag = 0;
}
void modify(int k, int l, int r, int x, int y, int v){
if(l >= x and r <= y){
t[k].sum += v * (r - l + 1);
t[k].tag += v;
return;
}
push_down(k, l, r);
int mid = l + r >> 1;
if(x <= mid) modify(lc, l, mid, x, y, v);
if(y > mid) modify(rc, mid+1, r, x, y, v);
push_up(k);
}
int ask(int k, int l, int r, int x){
if(l == r){
return t[k].sum;
}
push_down(k, l, r);
int mid = l + r >> 1;
if(x <= mid) return ask(lc, l, mid, x);
if(x > mid) return ask(rc, mid+1, r, x);
}
void build(int k, int l, int r){
t[k] = {0, 0}; if(l == r)return;
int mid = l + r >> 1;
build(lc, l, mid), build(rc, mid+1, r);
}
}Segment_trees[2];
int Y[N], n, T, m;
int maxy(0);
struct Union_Find{
int fa[N], L[N], R[N], siz[N];
void init(){
_for(i, 1, n){
fa[i] = i;
siz[i] = 1;
L[i] = R[i] = Y[i];
}
}
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void Union(int x, int y){
x = find(x), y = find(y);
if(x == y) return;
if(L[x] < R[x])
Segment_trees[0].modify(1, 1, maxy+1, L[x] + 1, R[x], -1),
Segment_trees[1].modify(1, 1, maxy+1, L[x] + 1, R[x], -siz[x]);
if(L[y] < R[y])
Segment_trees[0].modify(1, 1, maxy+1, L[y] + 1, R[y], -1),
Segment_trees[1].modify(1, 1, maxy+1, L[y] + 1, R[y], -siz[y]);
L[y] = min(L[y], L[x]);
R[y] = max(R[y], R[x]);
siz[y] = siz[x] + siz[y];
fa[x] = y;
if(L[y] < R[y])
Segment_trees[0].modify(1, 1, maxy+1, L[y] + 1, R[y], 1),
Segment_trees[1].modify(1, 1, maxy+1, L[y] + 1, R[y], siz[y]);
return;
}
}Sets;
int main(){
scanf("%d", &T);
while(T--){
scanf("%d", &n);
maxy = 0;
_for(i, 1, n){
static int x;
scanf("%d %d", &x, &Y[i]);
maxy = max(maxy, Y[i]);
}
Sets.init();
Segment_trees[0].build(1, 1, maxy+1);
Segment_trees[1].build(1, 1, maxy+1);
scanf("%d", &m);
char opt[11];
_for(i, 1, m){
scanf("%s", opt);
if(opt[0] == 'l'){
static int v;
static double y;
scanf("%lf", &y);
v = (int)floor(y + 0.6);
printf("%d %d\n", Segment_trees[0].ask(1, 1, maxy+1, v), Segment_trees[1].ask(1, 1, maxy+1, v));
}
else{
static int x, y;
scanf("%d %d", &x, &y);
x++, y++;
Sets.Union(x, y);
}
}
}
return 0;
}