存档

struct modint{
    int _v = 0;

    modint(long long x = 0){
        _v = x % P;
        if(_v < 0) _v += P;
    }

    modint operator+ (const modint &oy) const{
        return modint(_v + oy._v);
    }
    modint operator- (const modint &oy) const{
        return modint(_v - oy._v);
    }
    modint operator* (const modint &oy) const{
        return modint((long long)_v * oy._v);
    }

    modint &operator+= (const modint &oy){
        _v += oy._v;
        if(_v >= P) _v -= P;
        return *this;
    }
    modint &operator-= (const modint &oy){
        _v -= oy._v;
        if(_v < 0) _v += P;
        return *this;
    }
    modint &operator*= (const modint &oy){
        _v = ((long long)_v * oy._v) % P;
        return *this;
    }

    operator int() const{
        return _v;
    }
};

#include<bits/stdc++.h>

using namespace std;

namespace mycode{

const int N = 1e6 + 10;
const long long INF = 1e16;

int n, q;
long long a[N];

struct node{
	node *ls, *rs;
	int l, r;
	long long maxx, num, max2;
	long long sum;
	
	void pushup(){
		sum = ls->sum + rs->sum;
		maxx = max(ls->maxx, rs->maxx);
		if(ls->maxx == rs->maxx){
			num = ls->num + rs->num;
			max2 = max(ls->max2, rs->max2);
		}else{
			if(ls->maxx > rs->maxx){
				num = ls->num;
				max2 = max(ls->max2, max(rs->maxx, rs->max2));
			}else{
				num = rs->num;
				max2 = max(rs->max2, max(ls->maxx, ls->max2));
			}
		}
	}
	
	void build(int s, int t);
	
	void addtag(long long x){
		sum += (x-maxx) * num;
		maxx = x;
	}
	
	void pushdown(){
		if(ls->max2 <= maxx && maxx < ls->maxx){
			ls->addtag(maxx);
		}
		if(rs->max2 <= maxx && maxx < rs->maxx){
			rs->addtag(maxx);
		}
	}
	
	void cmin(int s, int t, int x){
		if(x >= maxx) return ;
		if(s <= l && r <= t){
			if(x > max2){
				addtag(x);
			}else{
				ls->cmin(s, t, x);
				rs->cmin(s, t, x);
				pushup();
			}
			return ;
		}
		pushdown();
		int mid = (l+r) / 2;
		if(s <= mid) ls->cmin(s, t, x);
		if(t > mid) rs->cmin(s, t, x);
		pushup();
	}
	
	long long qmax(int s, int t){
		if(s <= l && r <= t) return maxx;
		pushdown();
		int mid = (l+r) / 2;
		if(t <= mid) return ls->qmax(s, t);
		if(s > mid) return rs->qmax(s, t);
		return max(ls->qmax(s, t), rs->qmax(s, t));
	}
	
	long long qsum(int s, int t){
		if(s <= l && r <= t) return sum;
		pushdown();
		int mid = (l+r) / 2;
		if(t <= mid) return ls->qsum(s, t);
		if(s > mid) return rs->qsum(s, t);
		return ls->qsum(s, t) + rs->qsum(s, t);
	}
}st[N*2];
int ncnt;

void node::build(int s, int t){
	l = s; r = t;
	if(l == r){
		sum = maxx = a[l];
		num = 1;
		max2 = -INF;
		return ;
	}
	int mid = (l+r) / 2;
	ls = &st[++ncnt];
	rs = &st[++ncnt];
	ls->build(l, mid);
	rs->build(mid+1, r);
	pushup();
}

char buf[1 << 23], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
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 << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

void mymain(){
	
	int T = 0;
	T = read();
	while(T--){
		n = read();
		q = read();
		for(int i = 1; i <= n; i++){
			a[i] = read();
		}
		st[ncnt=1].build(1, n);
		int op = 0, x = 0, y = 0, z = 0;
		while(q--){
			op = read();
			x = read();
			y = read();
			if(op == 0){
				z = read();
				st[1].cmin(x, y, z);
			}
			if(op == 1){
				printf("%lld\n", st[1].qmax(x, y));
//				Fio::writell(st[1].qmax(x, y));
			}
			if(op == 2){
				printf("%lld\n", st[1].qsum(x, y));
//				Fio::writell(st[1].qsum(x, y));
			}
		}
	}
}

}

int main(){
	
	mycode::mymain();
	
	return 0;
}

struct LCT{

struct XD{
    int l, r;
    long double k, b;
}xd[N];
int xdcnt = 0;

long double f(XD fx, int x){
    return fx.k*x + fx.b;
}

int cmp(long double cx, long double cy){
    if(cx-cy > eps) return 1;
    if(cy-cx > eps) return -1;
    return 0;
}

int cmax(int cx, int cy, int x){
    if(!cx || !cy) return cx|cy;
    long double y1 = f(xd[cx], x), y2 = f(xd[cy], x);
    if(cmp(y1, y2) == 1 || (cmp(y1, y2)==0 && cx<cy)) return cx;
    return cy;
}

int rt, ncnt;
int ls[N], rs[N];
int maxx[N];

int New(){
    return ++ncnt;
}

void upd(int &p, int l, int r, int k){
    if(!p) p = New();
    if(!maxx[p]){
        maxx[p] = k;
        return ;
    }
    int mid = (l+r) / 2;
    if(cmax(maxx[p], k, mid) == k){
        swap(maxx[p], k);
    }
    if(cmax(maxx[p], k, l) == k){
        upd(ls[p], l, mid, k);
    }
    if(cmax(maxx[p], k, r) == k){
        upd(rs[p], mid+1, r, k);
    }
}

void add(int &p, int l, int r, int k){
    if(!p) p = New();
    if(xd[k].l <= l && r <= xd[k].r){
        upd(p, l, r, k);
        return ;
    }
    int mid = (l+r) / 2;
    if(xd[k].l <= mid) add(ls[p], l, mid, k);
    if(xd[k].r > mid) add(rs[p], mid+1, r, k);
}

int query(int p, int l, int r, int x){
    if(!p) return 0;
    if(l == r) return maxx[p];
    int mid = (l+r) / 2;
    if(x <= mid){
        return cmax(maxx[p], query(ls[p], l, mid, x), x);
    }else{
        return cmax(maxx[p], query(rs[p], mid+1, r, x), x);
    }
}

void insert(int x0, int y0, int x1, int y1){
    xdcnt++;
    xd[xdcnt].l = min(x0, x1);
    xd[xdcnt].r = max(x0, x1);
    if(x0 == x1){
        xd[xdcnt].k = 0;
        xd[xdcnt].b = max(y0, y1);
    }else{
        xd[xdcnt].k = ((long double)y1-y0) / (x1-x0);
        xd[xdcnt].b = y0-xd[xdcnt].k*x0;
    }
    add(rt, 1, V, xdcnt);
}

}lct;

struct LCT{

struct XD{
    int l, r;
    long long k, b;
}xd[N];
int xdcnt = 0;

long long f(XD fx, int x){
    return fx.k*x + fx.b;
}

int cmax(int cx, int cy, int x){
    if(!cx || !cy) return cx|cy;
    long long y1 = f(xd[cx], x), y2 = f(xd[cy], x);
    if(y1<y2) return cx;
    return cy;
}

int rt, ncnt;
int ls[M], rs[M];
int maxx[M];

int New(){
    return ++ncnt;
}

void upd(int &p, int l, int r, int k){
    if(!p) p = New();
    if(!maxx[p]){
        maxx[p] = k;
        return ;
    }
    int mid = (l+r) / 2;
    if(cmax(maxx[p], k, mid) == k){
        swap(maxx[p], k);
    }
    if(cmax(maxx[p], k, l) == k){
        upd(ls[p], l, mid, k);
    }
    if(cmax(maxx[p], k, r) == k){
        upd(rs[p], mid+1, r, k);
    }
}

void add(int &p, int l, int r, int k){
    if(!p) p = New();
    if(xd[k].l <= l && r <= xd[k].r){
        upd(p, l, r, k);
        return ;
    }
    int mid = (l+r) / 2;
    if(xd[k].l <= mid) add(ls[p], l, mid, k);
    if(xd[k].r > mid) add(rs[p], mid+1, r, k);
}

int query(int p, int l, int r, int x){
    if(!p) return 0;
    if(l == r) return maxx[p];
    int mid = (l+r) / 2;
    if(x <= mid){
        return cmax(maxx[p], query(ls[p], l, mid, x), x);
    }else{
        return cmax(maxx[p], query(rs[p], mid+1, r, x), x);
    }
}

long long query(int x){
    return f(xd[query(rt, 1, V, x)], x);
}

void insert(long long k, long long b, int l, int r){
    xdcnt++;
    xd[xdcnt].k = k;
    xd[xdcnt].b = b;
    xd[xdcnt].l = l;
    xd[xdcnt].r = r;
    add(rt, 1, V, xdcnt);
}

}lct;

来自江老师：

#include <bits/stdc++.h>
#include<bits/extc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using pii = pair<int, int>;

const int inf = 1e9;

tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> t;

int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        t.insert({x, -i});
    }
    int ans = 0, lst = 0;
    for (int i = 1; i <= m; i++) {
        int type, x;
        cin >> type >> x;
        x ^= lst;
        if (type == 1) t.insert({x, i});
        if (type == 2) t.erase(t.lower_bound({x, -inf}));
        if (type == 3) lst = t.order_of_key({x, -inf})+ 1, ans ^= lst;
        if (type == 4) lst = t.find_by_order(x - 1)->first, ans ^= lst;
        if (type == 5) lst = (*(--t.lower_bound({x, -inf}))).first, ans ^= lst;
        if (type == 6) lst = (*(t.upper_bound({x, inf}))).first, ans ^= lst;
    }
    cout << ans << '\n';
    return 0;
}

task：

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558
    // for the documentation about the tasks.json format
    "version": "2.0.0",
    "tasks": [
        {
            "label": "BianYi",
            "type": "shell",
            "command": "cd ${fileDirname} && g++ ${file} -o ./${fileBasenameNoExtension} -O2 -std=c++14 -Wall -Wextra -Wshadow -Wformat -fsanitize=undefined,address",
            "group": {
                "kind": "build",
                "isDefault": true
            }
        },
        {
            "label": "YunXing",
            "type": "shell",
            "command": "cd ${fileDirname} && ./${fileBasenameNoExtension}",
        }
        ,
        {
            "label": "CeSu",
            "type": "shell",
            "command": "cd ${fileDirname} && /bin/time -v ./${fileBasenameNoExtension}",
        }
    ]
}

快捷键：

// 将键绑定放在此文件中以覆盖默认值auto[]
[
    {
        "key": "ctrl+g",
        "command": "workbench.action.tasks.runTask",
        "args": "YunXing"
    } // 以此类推
]