#include<bits/stdc++.h>
using namespace std;
/*
1. 准备两个栈，数字栈和符号栈
2. 遇到数字进入数字栈，遇到符号比较优先级再入栈
3. 遇到左括号入符号栈，遇到右括号，计算到做括号为止
4. 计算栈中剩余的元素
*/
stack<char>op;
stack<int>num;
int main() {
	string s;
	cin >> s;
	for(int i = 0; i < s.size(); i++) {
		if(s[i]>='0' && s[i]<='9') {
			int sum = 0;
			while(s[i]>='0' && s[i]<='9') {
				sum = sum * 10 + s[i] - '0';
				i++;
			}
			i--;
			num.push(sum);
		} else if(s[i] == '(') {
			op.push(s[i]);
		} else if(s[i] == ')') {
			char c = op.top();
			op.pop();
			while(c != '(') {
//				cout << c << endl;
				int b = num.top();
				num.pop();
				int a = num.top();
				num.pop();

				if(c == '+')
					num.push(a+b);
				if(c == '-')
					num.push(a-b);
				if(c == '*')
					num.push(a*b);
				if(c == '/')
					num.push(a/b);
				c = op.top();
				op.pop();
			}
		} else {
			while(op.size() && (op.top() == '*' || op.top() == '/')) { // 栈顶优先级高于当前
				char c = op.top();
				op.pop();
				int b = num.top();
				num.pop();
				int a = num.top();
				num.pop();
				if(c == '*')
					num.push(a*b);
				if(c == '/')
					num.push(a/b);
			}

			op.push(s[i]);

		}
	}
	while(op.size()) {
		char c = op.top();
		op.pop();
		int b = num.top();
		num.pop();
		int a = num.top();
		num.pop();
		if(c == '+')
			num.push(a+b);
		if(c == '-')
			num.push(a-b);
		if(c == '*')
			num.push(a*b);
		if(c == '/')
			num.push(a/b);
	}
	cout << num.top();
	return 0;
}

线段树模板

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5, mod = 1e9+7;
int a[N], n, m;
int tr[N<<2], tag[N<<2];

void pushup(int k){
 	tr[k] = tr[k<<1] + tr[k<<1|1];
}

void build(int k, int l, int r){ // 当前结点k, 维护区间 [l, r] 
	if(l == r) {
		tr[k] = a[r];
		return ;
	}
	int mid = l + r >> 1;
	build(k<<1, l, mid);  	 //k<<1 => k*2
	build(k<<1|1, mid+1, r);  //k<<1|1 => k*2+1
	pushup(k);
}

void upd(int k, int l, int r, int w) { // 更新节点信息 
	tag[k] += w;
	tr[k] += (r-l+1)*w;
}

void pushdown(int k, int l, int r){ // 标记下放 
//	tag[k<<1] += tag[k];
	int mid = r+l>>1;
	upd(k<<1, l, mid, tag[k]);
//	tr[k<<1] += (mid-l+1) * tag[k]; // upd(k, l, r, w);
//	tag[k<<1|1] += tag[k];
//	tr[k<<1|1] += (r-mid)*tag[k];// r - (mid+1)+1
	upd(k<<1|1, mid+1, r, tag[k]);
	tag[k] = 0;
}

int query(int k, int l, int r, int x, int y){ 
	// k号结点，维护区间[l,r]。要查找的区间 [x, y]
	if(x <= l && r <= y){
		return tr[k];
	}
	int mid = l + r >> 1;
	pushdown(k, l, r);
	int ans = 0;
	if(x <= mid)  // 需要查询的区间有一部分在左孩子
		ans += query(k<<1, l, mid, x, y);
	if(y > mid) // 需要查询的区间有一部分在右孩子
		ans += query(k<<1|1, mid+1, r, x, y);
	return ans;
}



void modify(int k, int l, int r, int x, int y, int w){ 
// k号结点，维护额区间[l,r]  要给区间 [x, y]， +w 
	if(x <= l && r <= y){
//		tag[k] += w;
//		tr[k] += (r-l+1)*w;  // [l, r] + w
		upd(k, l, r, w); // 更新节点 
		return ;
	} 
	int mid = l + r >> 1;
	pushdown(k, l, r); // 向下传递 tag
	if(x <= mid) 
		modify(k<<1, l, mid, x, y, w);
	if(y > mid) 
		modify(k<<1|1, mid+1, r, x, y, w); 
	pushup(k);
}

signed main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	build(1, 1, n); 
	while(m--){
		int op, x, y, w;
		cin >> op;
		if(op == 1){
			cin >> x >> y >> w;
			modify(1, 1, n, x, y, w);
		} else {
			cin >> x >> y;
			cout << query(1, 1, n, x, y) << "\n";
		}
	}
	return 0;
}

策略游戏

/*
a正:
	b正: maxa * minb 
	b负/正负 ： mina * minb 
a:负
	b正负/正：maxa * maxb    
	b负：	mina * maxb 
a:正负 
	b正 maxa * minb 
	b负 mina * maxb
	b正/负
	max{mana+ * minb-, mina+ * minb-, maxa- * maxb+, mina- * maxb+};
	=> max(mina+ * minb, maxa- * maxb);
	
	需要 maxa,mina mina+,maxa-, maxb,minb 6个ST数组 
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5, mod = 1e9+7; // 1e5 * 6 * 20 + 2e5
int mxa[N][20], mna[N][20], mxb[N][20], mnb[N][20], mnaz[N][20], mxaf[N][20];
int a[N], b[N], n, m, q;
bool f1, f2;
int af[N], az[N], cntz, cntf;

void init(){
	for(int j = 1; 1<<j <= n; j++){
		for(int i = 1; i + (1<<j)-1 <= n; i++){
			mxa[i][j] = max(mxa[i][j-1], mxa[i+(1<<j-1)][j-1]); 
			mna[i][j] = min(mna[i][j-1], mna[i+(1<<j-1)][j-1]);
		}
	}
	
	for(int j = 1; 1<<j <= m; j++){
		for(int i = 1; i + (1<<j)-1 <= m; i++){
			mxb[i][j] = max(mxb[i][j-1], mxb[i+(1<<j-1)][j-1]);
			mnb[i][j] = min(mnb[i][j-1], mnb[i+(1<<j-1)][j-1]);
		}
	}
	

	for(int i = 1; i <= cntz; i++)
		mnaz[i][0] = az[i];
//	cout << cntz <<endl;
	for(int j = 1; 1<<j <= cntz; j++){
		for(int i = 1; i + (1<<j)-1 <= cntz; i++){
			mnaz[i][j] = min(mnaz[i][j-1], mnaz[i+(1<<j-1)][j-1]);
		}
	}

	
	for(int i = 1; i <= cntf; i++)
		mxaf[i][0] = af[i];

	for(int j = 1; 1<<j <= cntf; j++){
		for(int i = 1; i + (1<<j)-1 <= cntf; i++){
			mxaf[i][j] = max(mxaf[i][j-1], mxaf[i+(1<<j-1)][j-1]);
		}
	}
}


void solve(int l1, int r1, int l2, int r2){
	int k1 = log2(r1-l1+1), k2 = log2(r2-l2+1);
	int maxa = max(mxa[l1][k1], mxa[r1-(1<<k1)+1][k1]);
	int mina = min(mna[l1][k1], mna[r1-(1<<k1)+1][k1]);
	
	int maxb = max(mxb[l2][k2], mxb[r2-(1<<k2)+1][k2]);
	int minb = min(mnb[l2][k2], mnb[r2-(1<<k2)+1][k2]);
	
	int maxf = max(mxaf[l1][k1], mxaf[r1-(1<<k1)+1][k1]);
	int minz = min(mnaz[l1][k1], mnaz[r1-(1<<k1)+1][k1]);
	// 待验证 
//	cout << "###\n";
//	cout << maxa << " " << mina << "\n";
//	cout << maxb << " " << minb << "\n";
//	cout << maxf << " " << minz << "\n";
//	cout << "\n";
	if(mina >= 0) {
		if(minb >= 0){
			cout << maxa * minb;
		} else {
			cout << mina * minb;
		}
		
	} else if(maxa < 0) {
		if(maxb < 0){
			cout << mina * maxb; 
		} else {
			cout << maxa * maxb;  
		}
	} else {
		if(minb >= 0){
			cout << maxa * minb;
		} else if(maxb < 0){
			cout << mina * maxb;
		} else {
			cout << max(minz * minb, maxf * maxb);
		}
	}
	cout << endl;
}
signed main() {
	cin >> n >> m >> q;
	memset(az, 0x3f, sizeof az);
	memset(af, -0x3f, sizeof af); 
	cntz = cntf = n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		mxa[i][0] = a[i];
		mna[i][0] = a[i];
//		cout << mxa[i][0] << " ";
		if(a[i] >= 0) az[i] = a[i];
		else af[i] = a[i]; 
	}
//	cout << endl;
	for(int i = 1; i <= m; i++){
		cin >> b[i];
		if(b[i] >= 0) f1 = true;
		else f2 = true;
		mxb[i][0] = b[i];
		mnb[i][0] = b[i];
		
	}
	init();
	while(q--){
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		solve(l1, r1, l2, r2);
	}
	return 0;
}

廊桥分配

/*

[l, r]
按飞机的到达时间排序

给廊桥分配编号


1. 已经使用队列
2. 未使用队列

对于每个飞机，优先停在编号小得廊桥
    1. 先释放已使用队列
    2. 选出可以得廊桥，

*/

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct p{
    int l, r;
    bool operator < (const p p1) const{
        return l < p1.l;
    }
} a[N]; // 飞机

struct node{
    int r, id; 
    bool operator < (const node p) const{
        return r > p.r;
    }
}; // 已使用廊桥

int n, m1, m2;
int f1[N], f2[N];

void solve(int len, int f[]){
    sort(a+1, a+1+len);
    
    priority_queue<int, vector<int>, greater<int> > q2; // 未使用
    priority_queue<node> q1; // 已使用
    for(int i = 1; i <= len; i++)
        q2.push(i);
    
    for(int i = 1; i <= len; i++){
        while(q1.size() && q1.top().r < a[i].l){
            q2.push(q1.top().id);
            q1.pop();
        }

        if(!q2.size()) continue; 
        int id = q2.top();
        q2.pop();
        q1.push({a[i].r, id});

        f[id]++;
    }

    for(int i = 1; i <= n; i++){
        f[i] += f[i-1];
    }

}

int main(){

    cin >> n >> m1 >> m2;
    for(int i = 1; i <= m1; i++){
        cin >> a[i].l >> a[i].r;
    }
    solve(m1, f1);

    for(int i = 1; i <= m2; i++){
        cin >> a[i].l >> a[i].r;
    }
    solve(m2, f2);

    int ans = 0;
    for(int i = 0; i <= n; i++){
        ans = max(ans, f1[i] + f2[n-i]);
    }
    cout << ans;

    return 0;
}