2 条题解
-
0
#include <bits/stdc++.h> using namespace std; #define lc(p) (p<<1) #define rc(p) (p<<1|1) const int N=2e5+10; struct trnode{ int l,r,s,lazy; }tr[N<<2]; void pushup(int p) { tr[p].s=tr[lc(p)].s+tr[rc(p)].s; } void pushdown(int p) { if(tr[p].lazy) { tr[lc(p)].lazy^=1; tr[lc(p)].s=(tr[lc(p)].r-tr[lc(p)].l+1-tr[lc(p)].s); tr[rc(p)].lazy^=1; tr[rc(p)].s=(tr[rc(p)].r-tr[rc(p)].l+1-tr[rc(p)].s); tr[p].lazy=0; } } void bt(int p,int l,int r) { tr[p]={l,r,0,0}; if(l==r)return; int m=(l+r)>>1; bt(lc(p),l,m);bt(rc(p),m+1,r); } void change(int p,int l,int r) { if(r<tr[p].l||tr[p].r<l)return; if(l<=tr[p].l&&tr[p].r<=r) { tr[p].lazy^=1; tr[p].s=(tr[p].r-tr[p].l+1-tr[p].s); return; } pushdown(p); change(lc(p),l,r); change(rc(p),l,r); pushup(p); } int query(int p,int l,int r) { if(r<tr[p].l||tr[p].r<l) return 0; if(l<=tr[p].l&&tr[p].r<=r) return tr[p].s; pushdown(p); return query(lc(p),l,r)+query(rc(p),l,r); } int main() { int n,m;scanf("%d%d",&n,&m); bt(1,1,n); for(int i=1,L,R;i<=m;i++) { int c;scanf("%d%d%d",&c,&L,&R); if(!c) change(1,L,R); else printf("%d\n",query(1,L,R)); } return 0; } -
0
#include <bits/stdc++.h> using namespace std; #define lc(p) (p<<1) #define rc(p) (p<<1|1) const int N=2e5+10; struct trnode{ int l,r,s,lazy; }tr[N<<2]; void pushup(int p) { tr[p].s=tr[lc(p)].s+tr[rc(p)].s; } void pushdown(int p) { if(tr[p].lazy) { tr[lc(p)].lazy^=1; tr[lc(p)].s=(tr[lc(p)].r-tr[lc(p)].l+1-tr[lc(p)].s); tr[rc(p)].lazy^=1; tr[rc(p)].s=(tr[rc(p)].r-tr[rc(p)].l+1-tr[rc(p)].s); tr[p].lazy=0; } } void bt(int p,int l,int r) { tr[p]={l,r,0,0}; if(l==r)return; int m=(l+r)>>1; bt(lc(p),l,m);bt(rc(p),m+1,r); } void change(int p,int l,int r) { if(r<tr[p].l||tr[p].r<l)return; if(l<=tr[p].l&&tr[p].r<=r) { tr[p].lazy^=1; tr[p].s=(tr[p].r-tr[p].l+1-tr[p].s); return; } pushdown(p); change(lc(p),l,r); change(rc(p),l,r); pushup(p); } int query(int p,int l,int r) { if(r<tr[p].l||tr[p].r<l) return 0; if(l<=tr[p].l&&tr[p].r<=r) return tr[p].s; pushdown(p); return query(lc(p),l,r)+query(rc(p),l,r); } int main() { int n,m;scanf("%d%d",&n,&m); bt(1,1,n); for(int i=1,L,R;i<=m;i++) { int c;scanf("%d%d%d",&c,&L,&R); if(!c) change(1,L,R); else printf("%d\n",query(1,L,R)); } return 0; }
- 1
信息
- ID
- 2883
- 时间
- 2000ms
- 内存
- 16MiB
- 难度
- 6
- 标签
- 递交数
- 44
- 已通过
- 15
- 上传者