总是会有,不知道哪里有个 bug
#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int N = 1e6+5;
string s[N];
int n,m,a[N];
int l,r,op;
stack<string > t;
int pre[N],suf[N];
int tree[N<<2];
inline void build(int k,int l,int r){
if(l == r){
tree[k] = suf[l];
return ;
}
int mid = l + r >> 1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
tree[k] = min(tree[k<<1],tree[k<<1|1]);
}
inline int query(int k,int l,int r,int x,int y){
if(x <= l && r <= y)
return suf[k];
int mid = l+r >> 1,res=(int)1e6+5;
//if(l <= mid) res = query(k<<1,l,mid,x,y);
if(r > mid) res = min(res,query(k<<1|1,mid+1,r,x,y));
return res;
}
inline int singleQuery(int k,int l,int r,int x){
if(l == r)
return tree[l];
int mid = l+r >> 1;
if(x <= mid) return singleQuery(k<<1,l,mid,x);
return singleQuery(k<<1|1,mid+1,r,x);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> s[i];
if(s[i] == "pair") a[i] = -1;
else if(s[i] == "int") a[i] = 1;
pre[i] = pre[i-1]+a[i];
}
for(int i = n; i >= 1; i--)
suf[i] = suf[i+1]+a[i];
//for(int i = 1; i <= n; i++)
// cout << suf[i] << " ";
//cout << endl;
build(1,1,n);
for(int i = 1; i <= n; i++){
cout << singleQuery(1,1,n,i) << " ";
}cout << endl;
while(m--){
cin >> l >> r >> op;
bool b = true;
if(pre[r] - pre[l-1] != 1) b = false;
if(query(1,1,n,l,r)-suf[r+1] < 1) b = false;
cout << (b ? "Yes":"No") << endl;
cout << query(1,1,n,l,r) << endl;
if(op==1 && b){
for(int i = r; i >= l; i--){
if(s[i] == "int") t.push("int");
else if(s[i] == "pair"){
string p = t.top();
t.pop();
p = p+","+t.top();
t.pop();
t.push("pair<"+p+">");
}else if(s[i] == "vector"){
string p = t.top();
t.pop();
t.push("vector<"+p+">");
}
}
cout << t.top() << endl;
t.pop();
}
}
return 0;
}
/*
10 6
pair vector pair int vector int pair vector int int
5 6 0
3 6 0
8 10 0
7 10 1
1 10 1
2 5 1
*/
query 函数里面左子区间查询删掉就会有问题
x y 是查询区间
救救孩子吧一年没写线段树了 /kel