《算法竞赛进阶指南》 0x42 ~ 0x43 代码 + 杂谈

树状数组

楼兰图腾
逆序对

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2*1e5+10;

int c[maxn];
int n;
int lowbit(int x) {
	return x&(-x);
}

int ask(int x) {
	int res=0;
	for(; x; x-=x&(-x)) res+=c[x];
	return res;
}

void add(int x,int y) {
	for(; x<=n; x+=x&(-x)) {
		c[x]+=y;
	}
}

int a[maxn];
int L[maxn],R[maxn];
int l[maxn],r[maxn];

signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	add(a[1],1);
	for(int i=2;i<n;i++){
		add(a[i],1);
		l[i]=ask(n)-ask(a[i]);
		L[i]=ask(a[i]-1);
	}
	memset(c,0,sizeof c);
	add(a[n],1);
	for(int i=n-1;i>1;i--){
		add(a[i],1);
		R[i]=ask(a[i]-1);
		r[i]=ask(n)-ask(a[i]);
	}
	ll rs=0,res=0;
	for(int i=2;i<n;i++){
		rs+=1ll*l[i]*r[i];
		res+=1ll*L[i]*R[i]; 
	}
	cout<<rs<<" "<<res<<endl;
	return 0;
}

区间改 单点查

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=2*1e5+10;

int c[maxn];
int n;
int lowbit(int x) {
	return x&(-x);
}

int ask(int x) {
	int res=0;
	for(; x; x-=x&(-x)) res+=c[x];
	return res;
}

void add(int x,int y) {
	for(; x<=n; x+=x&(-x)) {
		c[x]+=y;
	}
}

int a[maxn];

signed main() {
	int m;
	cin>>n>>m;
	string cmd;
	int l,r,d;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=m;i++){
		cin>>cmd;
		if(cmd[0]=='Q'){
			cin>>l;
			cout<<ask(l)+a[l]<<endl;
		}else{
			cin>>l>>r>>d;
			add(l,d);
			add(r+1,-d);
		}
	}
	return 0;
}

区间改 区间查

建立2割数组维护

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

int a[maxn], n, m;
ll c[2][maxn], sum[maxn];

ll ask(int k, int x){
    ll res = 0;
    for(; x; x -=(-x&x)) res += c[k][x];
    return res;
}

void add(int k, int x, int y){
    for(; x <= n; x += (-x&x)) c[k][x] += y;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
    
    for(int i = 1; i <= m; i ++) {
        string cmd;
        int l, r, d;
        cin >> cmd >> l >> r;
        if(cmd[0] == 'C'){
            cin >> d;
            add(0, l, d);
            add(0, r + 1, -d);
            add(1, l, l * d);
            add(1, r + 1, -(r + 1) * d);
        }else{
            ll ans = sum[r] + (r + 1) * ask(0, r) - ask(1, r);
            ans -= sum[l - 1] + l * ask(0, l - 1) - ask(1, l - 1);
            cout << ans << endl;
        }   
    }
    return 0;
}

lost cow
找第K大 我之前写的 链接https://www.acwing.com/solution/AcWing/content/2166/
二分 树状数组

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

int c[maxn];
int n;

int query(int x){
    int res = 0;
    for(; x; x -= x&(-x)) res += c[x];
    return res;
}

void add(int x, int y){
    for(;x <= n; x += x & (-x)) c[x] += y;
}

int a[maxn];
int ans[maxn];
int main(){
    cin >> n;
    add(1, 1);
    a[1] ++;
    for(int i = 2; i <= n ; i ++ ) {
        cin >> a[i]; a[i] ++;
        add(i, 1);
    }
    for(int i = n; i >= 1; i -- ) {
        int l = 1, r = n + 1;
        while(r - l >= 1){
            int mid = l + r >> 1;
            if(query(mid) >= a[i]) r = mid;
            else l = mid + 1;
        }
        ans[i] = l;
        add(l, -1);
    }
    for(int i = 1; i <= n; i ++ ) {
        cout << ans[i] << endl;
    }
    return 0;
}

线段树

can you answer on these queries III
区间最大子段和
pushup 函数修改 以及每一次上传的这次修改区间之后 整体的信息 而不是单独区间和的改变

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0)
const int maxn = 5e5+10;
int n, m;

int sum[maxn << 2], lmax[maxn << 2], rmax[maxn << 2], lrmax[maxn << 2];

void push_up(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	lmax[rt] = max(lmax[rt << 1], sum[rt << 1] + lmax[rt << 1 | 1]);
	rmax[rt] = max(rmax[rt << 1 | 1], sum[rt << 1 | 1] + rmax[rt << 1]);
	lrmax[rt] = max( max(lrmax[rt << 1], lrmax[rt << 1 | 1]), rmax[rt << 1] + lmax[rt << 1 | 1]);
}

void update(int L, int l, int r, int rt, int c) {
	if(l == r) {
		lrmax[rt] = lmax[rt] = rmax[rt] = sum[rt] = c;
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update(L, l, mid, rt << 1, c);
	else update(L, mid + 1, r, rt << 1 | 1, c);
	push_up(rt);
}

struct node {
	int sum;
	int lmax, rmax, lrmax;
};

node query(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return node {sum[rt], lmax[rt], rmax[rt], lrmax[rt]};
	}
	int mid = l + r >> 1;
	if (R <= mid) return query(L, R, l, mid, rt << 1);
	else if (L > mid) return query(L, R, mid + 1, r, rt << 1 | 1);
	else {
		node res;
		node re1 = query (L, R, l, mid, rt << 1);
		node re2 = query (L, R, mid + 1, r, rt << 1 | 1);
		res.sum = re1.sum + re2.sum;
		res.lmax = max(re1.lmax, re1.sum + re2.lmax);
		res.rmax = max(re2.rmax, re2.sum + re1.rmax);
		res.lrmax = max( max(re1.lrmax, re2.lrmax), re1.rmax + re2.lmax);
		return res;
	}
}

int main() {
	fastio;
	cin >> n >> m;
	int k;
	for(int i = 1; i <= n; i ++) {
		cin >> k;
		update(i, 1, n, 1, k);
	}
	while(m--) {
		int cmd, x ,y;
		cin >> cmd >> x >> y;
		if(cmd == 1) {
			if(x > y) swap (x, y);
			cout << query(x, y, 1, n, 1).lrmax << endl;
		} else {
			update(x, 1, n, 1, y);
		}
	}
	return 0;
}

区间最大公约数
差分 后 GCD 不变 注意越界问题

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(false);cin.tie(0)

const int maxn = 5e5+10;
int n, m;
int a[maxn],b[maxn],c[maxn];

struct node {
	int val;
} tree[maxn << 2];

int gcd(int a, int b) {
	return b == 0 ? a : gcd (b, a%b);
}

void push_up(int rt) {
	tree[rt].val = gcd(tree[rt << 1].val, tree[rt << 1 | 1].val);
}

void build(int l, int r, int rt) {
	if(l == r) {
		tree[rt].val = b[l];
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	push_up(rt);
}

void update(int L, int l, int r, int rt, int c) {
	if(L > n) return ; // wc 这里什么鬼啊 越界到什么一个位置了 
// 这里 L > n 的话 最后一个点 差分 被 暴力改掉了 导致gcd错误 
// 这bug真实难找orz 
	if(l == r) {
		tree[rt].val += c;
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update(L, l, mid, rt << 1, c);
	else update(L, mid + 1, r, rt << 1 | 1, c);
	push_up(rt);
}

int query(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return abs(tree[rt].val);
	}
	int mid = l + r >> 1;
	int x = 0, y = 0;
	if(L <= mid) x=query(L, R, l, mid, rt << 1);
	if(R > mid) y=query(L, R, mid + 1, r, rt << 1 | 1);
	return gcd(x, y);
}

int ask(int x) {
	int res=0;
	for(; x; x -= (-x) & x) {
		res += c[x];
	}
	return res;
}

int add(int x, int y) {
	for(; x <= n; x += (-x) & x ) {
		c[x] += y;
	}
}

signed main() {
	fastio; 
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		b[i] = a[i] - a[i - 1];
	}
	build(1, n, 1);
	string cmd;
	int l, r, d;
	for(int i = 1; i <= m ; i ++ ) {
		cin >> cmd >> l >> r;
		if(cmd[0] == 'C') {
			cin >> d;
			update(l, 1, n, 1, d);
			update(r + 1, 1, n, 1, -d);
			add(l, d);
			add(r + 1, -d);
		} else {
			cout << gcd(a[l] + ask(l), query(l + 1, r, 1, n, 1)) << endl;
		}
	}
	return 0;
}

扫描线

题集 链接 https://blog.csdn.net/qq_40831340/article/details/90698827
言特兰蒂斯
此时线段树 每个节点都有意义 都代表一些线段的组合

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define db double

const int maxn = 2005;

struct node {
	double lx,rx,y;
	int s;
	node() {}
	node(db _lx, db _rx, db _y, int _s) {
		lx=_lx, rx=_rx, y=_y, s=_s;
	}
	bool operator < (const node &S) const {
		return y<S.y;
	}
} lines[maxn];

db X[maxn];

db sum[maxn<<2],flag[maxn<<2];

void push_up(int rt, int l, int r) {
	if(flag[rt])
		sum[rt] = X [ r+1] - X[ l];
	else if(l == r)
		sum[rt] = 0;
	else
		sum[rt] = sum[rt << 1] + sum[rt << 1|1];
}

void update(int L, int R, int l, int r, int rt, int c) {
	if(L <= l && r <= R) {
		flag[rt]+=c;
		push_up(rt, l, r);
		return ;
	}
	int mid = (l + r) >> 1;
	if(L <= mid) update(L, R, l, mid, rt << 1, c);
	if(R > mid) update(L, R, mid + 1, r, rt << 1|1, c);
	push_up(rt, l, r);
}

int main() {
	int cas=1;
	int n;
	while(cin >> n, n) {
		int cnt = 0;
		memset(sum, 0, sizeof sum);
		memset(flag, 0, sizeof flag);
		for(int i = 1; i <= n; i ++ ) {
			double x1, x2, y1, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			X[ ++cnt ] = x1;
			lines[ cnt ] = node(x1, x2, y1, 1);
			X[ ++cnt ]= x2;
			lines[ cnt ] = node(x1, x2, y2, -1);
		}
		sort(X + 1, X + 1 + cnt);
		sort(lines + 1, lines + 1 + cnt);
		int pos = unique(X + 1, X + 1 + cnt) - X;
		db ans = 0;

		for(int i = 1; i < cnt; i ++ ) {
			int l = lower_bound(X + 1, X + pos, lines[ i ].lx) - X;
			int r = lower_bound(X + 1, X + pos, lines[ i ].rx) - X - 1;
			update(l, r, 1, cnt , 1, lines[i].s);
			ans += sum[ 1 ] * (lines[ i+1 ].y - lines[ i ].y);
		}
		cout << "Test case #" << cas++ << endl;
		cout << "Total explored area: ";
		printf("%.2lf\n\n",ans);
	}
	return 0;
}