1690 开关灯
USACO
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)
输入描述 Input Description
第 1 行: 用空格隔开的两个整数N和M
第 2..M+1 行: 每行表示一个操作, 有三个用空格分开的整数: 指令号(0代表按下开关，1代表询问状态), x 和 y
输出描述 Output Description
第 1..询问总次数 行:对于每一次询问，输出询问的结果
样例输入 Sample Input
4 5
0 1 20 2 41 2 30 2 41 1 4 样例输出 Sample Output
1 2
数据范围及提示 Data Size & Hint
一共4盏灯，5个操作，下面是每次操作的状态(X代表关上的，O代表开着的)：
XXXX -> OOXX -> OXOO -> 询问1~3 -> OOXX -> 询问1~4
分类标签 Tags
线段树练习
#include#include #include #define N 2000010#define lc k<<1#define rc k<<1|1using namespace std;struct node{ int l,r,v; bool lazy;}a[N];int read(){ register int f=1,x=0; register char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}void ins(int k,int l,int r){ a[k].l=l;a[k].r=r; if(l==r) return; int mid=(l+r)>>1; ins(lc,l,mid); ins(rc,mid+1,r);}void pushdown(int k){ if(!a[k].lazy) return; a[lc].lazy=!a[lc].lazy; a[rc].lazy=!a[rc].lazy; a[lc].v=a[lc].r-a[lc].l+1-a[lc].v; a[rc].v=a[rc].r-a[rc].l+1-a[rc].v; a[k].lazy=0;}void add(int k,int x,int y){ pushdown(k); int l=a[k].l,r=a[k].r; if(l==x&&r==y){ a[k].v=y-x+1-a[k].v; if(l!=r) a[k].lazy=1; return ; } int mid=(l+r)>>1; if(y<=mid) add(lc,x,y); else if(x>mid) add(rc,x,y); else add(lc,x,mid),add(rc,mid+1,y); a[k].v=a[lc].v+a[rc].v;}int query(int k,int x,int y){ pushdown(k); int l=a[k].l,r=a[k].r; if(l==x&&r==y) return a[k].v; int mid=(l+r)>>1; if(y<=mid) return query(lc,x,y); else if(x>mid) return query(rc,x,y); else return (query(lc,x,mid)+query(rc,mid+1,y)); }int main(){ int n=read(),q=read(); ins(1,1,n); for(int i=1;i<=q;i++){ int opt=read(),l=read(),r=read(); if(opt==0) add(1,l,r); else printf("%d\n",query(1,l,r)); } return 0;}
自己没看题解写的
#includeusing namespace std;struct node{ int l,r,lch,rch,v; bool tag;}tr[401000];int cnt;void build(int k,int l,int r){ cnt++; tr[cnt].l=l;tr[cnt].r=r; if(l==r) return ; int mid=(l+r)>>1; tr[k].lch=cnt+1; build(cnt+1,l,mid); tr[k].rch=cnt+1; build(cnt+1,mid+1,r); //tr[k].v=tr[tr[k].lch].v+tr[tr[k].rch].v;}void pushdown(int k){ if(!tr[k].tag) return ; tr[tr[k].lch].v=tr[tr[k].lch].r-tr[tr[k].lch].l+1-tr[tr[k].lch].v; tr[tr[k].rch].v=tr[tr[k].rch].r-tr[tr[k].rch].l+1-tr[tr[k].rch].v; tr[tr[k].lch].tag=!tr[tr[k].lch].tag; tr[tr[k].rch].tag=!tr[tr[k].rch].tag; tr[k].tag=0;}void add(int k,int x,int y){ int l=tr[k].l,r=tr[k].r; if(l==x&&r==y){ tr[k].v=y-x+1-tr[k].v; if(l!=r) tr[k].tag=!tr[k].tag; return ; } pushdown(k); int mid=(l+r)>>1; if(y<=mid) add(tr[k].lch,x,y); else if(x>mid) add(tr[k].rch,x,y); else add(tr[k].lch,x,mid),add(tr[k].rch,mid+1,y); tr[k].v=tr[tr[k].lch].v+tr[tr[k].rch].v;}int query(int k,int x,int y){ int l=tr[k].l,r=tr[k].r; if(l==x&&r==y) return tr[k].v; pushdown(k); int mid=(l+r)>>1; if(y<=mid) return query(tr[k].lch,x,y); else if(x>mid) return query(tr[k].rch,x,y); else return query(tr[k].lch,x,mid)+query(tr[k].rch,mid+1,y);}int main(){ int n,m,opt,l,r; scanf("%d%d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++){ scanf("%d%d%d",&opt,&l,&r); if(!opt){ add(1,l,r); } else{ printf("%d\n",query(1,l,r)); } }}
最新版
#include#define lc k<<1#define rc k<<1|1using namespace std;inline int read(){ register int x=0;bool f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return f?x:-x;}const int N=1e5+10;const int M=N<<2;int n,m,t1[N],a[M],tag[M];/*void build(int k,int l,int r){ if(l==r){ a[k]=0;return ; } int mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); a[k]=a[lc]+a[rc];}*/void pushdown(int k,int l,int r){ if(!tag[k]) return ; tag[lc]^=1; tag[rc]^=1; int mid=l+r>>1; a[lc]=(mid-l+1)-a[lc]; a[rc]=(r-mid)-a[rc]; tag[k]=0;}void change(int k,int l,int r,int x,int y){ if(l==x&&r==y){ a[k]=(y-x+1)-a[k]; tag[k]^=1; return ; } pushdown(k,l,r); int mid=l+r>>1; if(y<=mid) change(lc,l,mid,x,y); else if(x>mid) change(rc,mid+1,r,x,y); else change(lc,l,mid,x,mid),change(rc,mid+1,r,mid+1,y); a[k]=a[lc]+a[rc];}int query(int k,int l,int r,int x,int y){ if(l==x&&r==y) return a[k]; pushdown(k,l,r); int mid=l+r>>1; if(y<=mid) return query(lc,l,mid,x,y); else if(x>mid) return query(rc,mid+1,r,x,y); else return query(lc,l,mid,x,mid)+query(rc,mid+1,r,mid+1,y);}int main(){ n=read(); //build(1,1,n); m=read(); for(int i=1,opt,x,y,z;i<=m;i++){ opt=read(); if(!opt){ x=read();y=read(); change(1,1,n,x,y); } else{ x=read();y=read(); printf("%d\n",query(1,1,n,x,y)); } } return 0;}