题目:需要巩固
hanker_AFO · · 个人记录
平衡树
P2584 [ZJOI2006]GameZ游戏排名系统-Treap版
P4291 [HAOI2008]排名系统-Splay版
(以上两题为重题,但数据不同)
P1110 ZJOI2007报表统计
P1486 NOI2004郁闷的出纳员
P2596 ZJOI2006书架
P2042 NOI2005维护数列
扫描线
P1856 [USACO5.5]矩形周长Picture
差分约束
#10088. 「一本通 3.4 例 2」出纳员问题
剩余系
P2662 牛场围栏
网络流
P4174 NOI2006最大获利
P1486 NOI2004郁闷的出纳员
P2857 USACO06FEB稳定奶牛分配Steady Cow Assignment
P2754 CTSC1999家园
线段树
P2572 [SCOI2010]序列操作 注意操作优先级, [code]
#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define ls (nod<<1)
#define rs (nod<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
int read(){
int x=0; char c; int flag=1;
for(c=getchar();!isdigit(c);c=getchar()) if(c=='-') flag=-1;
for(;isdigit(c);c=getchar()) x=((x+(x<<2))<<1)+(c^48);
return x*flag;
}
const int N=1e5+50;
int n,m;
struct node{
int l,r;
int len;
int tag;
int rev;
int l0,r0,s0,x0;
int l1,r1,s1,x1;
}t[N<<2];
void pushup(int nod){
if(t[nod].l==t[nod].r) return ;
if(t[ls].l0==t[ls].len) t[nod].l0=t[ls].l0+t[rs].l0; else t[nod].l0=t[ls].l0;
if(t[ls].l1==t[ls].len) t[nod].l1=t[ls].l1+t[rs].l1; else t[nod].l1=t[ls].l1;
if(t[rs].r0==t[rs].len) t[nod].r0=t[rs].r0+t[ls].r0; else t[nod].r0=t[rs].r0;
if(t[rs].r1==t[rs].len) t[nod].r1=t[rs].r1+t[ls].r1; else t[nod].r1=t[rs].r1;
t[nod].s0=t[ls].s0+t[rs].s0;
t[nod].s1=t[ls].s1+t[rs].s1;
t[nod].x0=max(max(t[ls].x0,t[rs].x0),t[ls].r0+t[rs].l0);
t[nod].x1=max(max(t[ls].x1,t[rs].x1),t[ls].r1+t[rs].l1);
}
void pushdown(int nod){
if(t[nod].l==t[nod].r) return ;
if(t[nod].tag!=-1){
int x=t[nod].tag; t[nod].tag=-1;
if(x==0){
t[ls].l0=t[ls].r0=t[ls].s0=t[ls].x0=t[ls].len;
t[ls].l1=t[ls].r1=t[ls].s1=t[ls].x1=0;
t[rs].l0=t[rs].r0=t[rs].s0=t[rs].x0=t[rs].len;
t[rs].l1=t[rs].r1=t[rs].s1=t[rs].x1=0;
}
else{
t[ls].l0=t[ls].r0=t[ls].s0=t[ls].x0=0;
t[ls].l1=t[ls].r1=t[ls].s1=t[ls].x1=t[ls].len;
t[rs].l0=t[rs].r0=t[rs].s0=t[rs].x0=0;
t[rs].l1=t[rs].r1=t[rs].s1=t[rs].x1=t[rs].len;
}
t[ls].tag=t[rs].tag=x;
t[ls].rev=t[rs].rev=0;
}
if(t[nod].rev!=0){
t[nod].rev=0;
t[ls].rev^=1; t[rs].rev^=1;
swap(t[ls].l0,t[ls].l1); swap(t[ls].r0,t[ls].r1);
swap(t[ls].s0,t[ls].s1); swap(t[ls].x0,t[ls].x1);
swap(t[rs].l0,t[rs].l1); swap(t[rs].r0,t[rs].r1);
swap(t[rs].s0,t[rs].s1); swap(t[rs].x0,t[rs].x1);
}
}
void build(int nod,int l,int r){
t[nod].l=l; t[nod].r=r; t[nod].len=r-l+1;
t[nod].tag=-1; t[nod].rev=0;
if(l==r){
int x=read();
if(x==1) t[nod].l1=t[nod].r1=t[nod].s1=t[nod].x1=1;
else t[nod].l0=t[nod].r0=t[nod].s0=t[nod].x0=1;
return ;
}
build(lson); build(rson);
pushup(nod);
}
void update(int nod,int l,int r,int ll,int rr,int v){
if(l==ll&&r==rr){
if(v==0){
t[nod].tag=0; t[nod].rev=0;
t[nod].l1=t[nod].r1=t[nod].s1=t[nod].x1=0;
t[nod].l0=t[nod].r0=t[nod].s0=t[nod].x0=t[nod].len;
}else if(v==1){
t[nod].tag=1; t[nod].rev=0;
t[nod].l1=t[nod].r1=t[nod].s1=t[nod].x1=t[nod].len;
t[nod].l0=t[nod].r0=t[nod].s0=t[nod].x0=0;
}else if(v==2){
t[nod].rev^=1;
swap(t[nod].l1,t[nod].l0);swap(t[nod].r1,t[nod].r0);
swap(t[nod].s1,t[nod].s0);swap(t[nod].x1,t[nod].x0);
}
return ;
}
pushdown(nod);
if(rr<=mid) update(lson,ll,rr,v);
else if(ll>mid) update(rson,ll,rr,v);
else update(lson,ll,mid,v),update(rson,mid+1,rr,v);
pushup(nod);
}
node query(int nod,int l,int r,int ll,int rr){
if(l==ll&&r==rr) return t[nod];
pushdown(nod);
if(rr<=mid) return query(lson,ll,rr);
else if(ll>mid) return query(rson,ll,rr);
else{
node tmp1=query(lson,ll,mid);
node tmp2=query(rson,mid+1,rr);
node tmp;
tmp.l=l; tmp.r=r; tmp.len=r-l+1;
if(tmp1.l0==tmp1.len) tmp.l0=tmp1.l0+tmp2.l0; else tmp.l0=tmp1.l0;
if(tmp1.l1==tmp1.len) tmp.l1=tmp1.l1+tmp2.l1; else tmp.l1=tmp1.l1;
if(tmp2.r0==tmp2.len) tmp.r0=tmp2.r0+tmp1.r0; else tmp.r0=tmp2.r0;
if(tmp2.r1==tmp2.len) tmp.r1=tmp2.r1+tmp1.r1; else tmp.r1=tmp2.r1;
tmp.s0=tmp1.s0+tmp2.s0;
tmp.s1=tmp1.s1+tmp2.s1;
tmp.x0=max(max(tmp1.x0,tmp2.x0),tmp1.r0+tmp2.l0);
tmp.x1=max(max(tmp1.x1,tmp2.x1),tmp1.r1+tmp2.l1);
return tmp;
}
}
signed main() {
n=read(),m=read();
build(1,1,n);
while(m--){
int opt=read(),l=read()+1,r=read()+1;
if(opt<=2) update(1,1,n,l,r,opt);
else{
node tmp=query(1,1,n,l,r);
if(opt==3) printf("%d\n",tmp.s1);
else printf("%d\n",tmp.x1);
}
}
return 0;
}P1438 无聊的数列 树状数组的区间修改,区间查询
[code]
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0; char c; int flag=1;
for(c=getchar();!isdigit(c);c=getchar()) if(c=='-') flag=-1;
for(;isdigit(c);c=getchar()) x=((x+(x<<2))<<1)+(c^48);
return x*flag;
}
const int N=1e5+50;
int n,m;
int a[N];
int c[N],d[N];
int lowbit(int x){
return x&(-x);
}
int query(int x){
int ret=0;
for(int i=x;i>0;i-=lowbit(i)) ret+=(x+1)*c[i]-d[i];
return ret;
}
void update(int x,int y){
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y,d[i]+=x*y;
}
void qj(int l,int r,int v){
update(l,v);
update(r+1,-v);
}
signed main() {
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
while(m--){
int opt=read();
if(opt==1){
int l=read(),r=read(),k=read(),D=read();
qj(l,l,k);
qj(l+1,r,D);
qj(r+1,r+1,-k-D*(r-l));
}
else{
int p=read();
printf("%d\n",query(p)+a[p]);
}
}
return 0;
}杂题
[ZJOI2003] 密码机
树状数组维护异或和
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0; char c; int flag=1;
for(c=getchar();!isdigit(c);c=getchar()) if(c=='-') flag=-1;
for(;isdigit(c);c=getchar()) x=((x+(x<<2))<<1)+(c^48);
return x*flag;
}
const int N=2e5;
int c[N+10];
int lowbit(int x) { return x&(-x); }
void update(int x){
for(int i=x;i<=N;i+=lowbit(i))
c[i]^=x;
}
int query(int x){
int ret=0;
for(int i=x;i>0;i-=lowbit(i)) ret^=c[i];
return ret;
}
int main() {
char opt;
while(scanf(" %c",&opt)!=EOF){
if(opt=='A'){
int x;
scanf("DD %d",&x);
update(x);
}else if(opt=='R'){
int x;
scanf("EMOVE %d",&x);
update(x);
}else{
int x,y;
scanf("OR BETWEEN %d AND %d",&x,&y);
if(x>y) printf("0\n");
else
printf("%d\n",query(y)^query(x-1));
}
}
return 0;
}