调了整整5个小时,结果发现自己建树的方式有误,气死我了气死我了,比较好的一道线段树(虽然我不会-----
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,res,point; vector<int>v[2]; // 用于存储结果的数组，下标0表示sum为0，下标1表示sum为1 struct node { int l,r,sum,add; // l表示左端点，r表示右端点，sum表示[l, r]区间内sum的个数，add表示懒惰标记 }tr[N*2]; // 线段树的节点数组 void pushup(int u) { tr[u].sum=tr[2*u].sum+tr[2*u+1].sum; // 合并子节点的sum值更新父节点的sum值 } void pushdown(int u) { if(tr[u].add==-1) return; // 如果没有懒惰标记，直接返回 auto &root=tr[u],&left=tr[2*u],&right=tr[2*u+1]; // 引用父节点、左子节点、右子节点 left.add=root.add,left.sum=(left.r-left.l+1)*root.add; // 更新左子节点的懒惰标记和sum值 right.add=root.add,right.sum=(right.r-right.l+1)*root.add; // 更新右子节点的懒惰标记和sum值 root.add=-1; // 清除父节点的懒惰标记 } void build(int u,int l,int r) { if(l==r) tr[u]={l,r,1,-1}; // 叶节点初始化，sum为1，懒惰标记为-1 else{ tr[u]={l,r}; // 非叶节点初始化 int mid=(l+r)>>1; build(2*u,l,mid); // 递归构建左子树 build(2*u+1,mid+1,r); // 递归构建右子树 pushup(u); // 合并子节点的信息更新父节点 } } void modify1(int u,int val) { int num=tr[u].r-tr[u].l+1-tr[u].sum; // 当前节点区间内0的个数 if(num<=val){ tr[u].sum=tr[u].r-tr[u].l+1; tr[u].add=1; // 更新懒惰标记为1，表示当前区间内的sum全部变为1 return; } pushdown(u); // 将当前节点的懒惰标记下传到子节点 auto &left=tr[2*u],&right=tr[2*u+1]; int l_num=left.r-left.l+1-left.sum; // 左子节点区间内0的个数 int r_num=right.r-right.l+1-right.sum; // 右子节点区间内0的个数 if(l_num>=val) modify1(2*u,val); // 如果左子节点区间内的0个数足够，递归更新左子节点 else modify1(2*u,l_num),modify1(2*u+1,val-l_num); // 否则分别更新左右子节点 pushup(u); // 更新当前节点的信息 } void modify0(int u,int val) { int num=tr[u].sum; // 当前节点区间内1的个数 if(val>=num){ tr[u].sum=0,tr[u].add=0; // 更新当前节点的sum为0，懒惰标记为0 return; } pushdown(u); // 将当前节点的懒惰标记下传到子节点 auto &left=tr[2*u],&right=tr[2*u+1]; int l_num=left.sum; // 左子节点区间内1的个数 int r_num=right.sum; // 右子节点区间内1的个数 if(l_num>=val) modify0(2*u,val); // 如果左子节点区间内的1个数足够，递归更新左子节点 else modify0(2*u,l_num),modify0(2*u+1,val-l_num); // 否则分别更新左右子节点 pushup(u); // 更新当前节点的信息 } int query(int u,int pos) { if(tr[u].l==tr[u].r) return tr[u].sum; // 叶节点直接返回sum值 pushdown(u); // 将当前节点的懒惰标记下传到子节点 int mid=tr[u].l+tr[u].r>>1; if(pos<=mid) return query(2*u,pos); // 根据位置递归查询左子树或右子树 else return query(2*u+1,pos); } int main() { cin>>n>>m; build(1,1,n); // 构建线段树 point=1; while(m--){ int op,x; cin>>op>>x; if(op==1){ if(point<=x) continue; modify1(1,point-x); // 将前面的0变为1 point=x; } else{ if(point>x) continue; modify0(1,x-point+1); // 将后面的1变为0 point=x+1; } } for(int i=1;i<=n;i++){ if(query(1,i)==0) v[0].push_back(i); // 根据sum值判断属于哪个分组 else v[1].push_back(i); } for(int i=v[0].size()-1;i>=0;i--) cout<<v[0][i]<<" "; // 输出结果 for(int i=0;i<v[1].size();i++) cout<<v[1][i]<<" "; return 0; }