QAQ 一个区间赋值的题目,将黑色赋值为1,白色赋值为0,统计区间和就行了 同样采用懒标记的思想 至于变量类型,由于是在一个题目上改过来的,于是乎,就开了long long型,所以有点慢,不过实在是懒得改了
#include <iostream> #include <cstdio> #define ll long long using namespace std; struct tree{ ll sum,r,l,len,adi; }st[201000<<2]; ll a[201000]; void build(int o,int l,int r) { st[o].l=l,st[o].r=r,st[o].len=r-l+1; if(l==r) { st[o].sum=a[l]; return; } int mid=(r+l)>>1; build((o<<1),l,mid); build((o<<1)|1,mid+1,r); st[o].sum=st[(o<<1)].sum+st[(o<<1)|1].sum; } void push_down(int o) { st[o].adi=0; st[(o<<1)].adi=1; st[(o<<1)|1].adi=1; st[(o<<1)].sum=0; st[(o<<1)|1].sum=0; } void query(int o,int ql,int qr) { int l=st[o].l,r=st[o].r,len=st[o].len; if(l==ql&&r==qr) { st[o].adi=1; st[o].sum=0; return; } if(st[o].adi) push_down(o); int mid=(l+r)>>1; if(qr<=mid) query((o<<1),ql,qr); else if(ql>mid) query((o<<1)|1,ql,qr); else query((o<<1),ql,mid),query((o<<1)|1,mid+1,qr); st[o].sum=st[(o<<1)].sum+st[(o<<1)|1].sum; } ll ask(int o,int ql,int qr) { int l=st[o].l,r=st[o].r,len=st[o].len; if(l==ql&&r==qr) return st[o].sum; if(st[o].adi) push_down(o); int mid=(l+r)>>1; if(qr<=mid) return ask((o<<1),ql,qr); else if(ql>mid) return ask((o<<1)|1,ql,qr); else return (ask((o<<1),ql,mid)+ask((o<<1)|1,mid+1,qr)); } int main() { int n,m; scanf("%d",&n); scanf("%d",&m); for(int i=1;i<=n;i++) a[i]=1; build(1,1,n); for(int i=1;i<=m;i++) { int x,a,b; scanf("%d%d",&a,&b); query(1,a,b); printf("%lld\n",ask(1,1,n)); } return 0; }方法2:并查集维护 这个题主要是可能重复染色,大大拖慢的运行的速度,那么我们使用并查集维护,将确定的点的父节点设为前一个节点就行了
#include<cstdio> using namespace std; int fat[200000+100]; int find(int x) { if(x==fat[x]) return x; return fat[x]=find(fat[x]); } int n,m; int main() { scanf("%d%d",&n,&m); int ans=n; for(int i=1;i<=n;i++) fat[i]=i; for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); int f1=find(a-1); for(;f1!=find(b);) fat[find(b)]=find(b)-1,ans--; printf("%d\n",ans); } return 0; }