每次写线段树特有的反应
  • 板块学术版
  • 楼主Lovely_Elaina
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/7 15:40
  • 上次更新2024/8/7 16:24:42
查看原帖
每次写线段树特有的反应
781159
Lovely_Elaina楼主2024/8/7 15:40

总是会有,不知道哪里有个 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

2024/8/7 15:40
加载中...