Lvat_s Blog

Link-Cut Tree直接上……

但是因为智商原因2天才能理解+写会这个东西。

因为BZOJ爆了所以测不了。但是和hzwer的程序对拍了没拍出什么错误。。。在BZOJ上AC了

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m;

struct Node{
int v,ans,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root[300005],*Null;

Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=ans=val;
rev=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
}

void Node::Pushup(){
ans=v;
if(ch[0]!=Null)ans^=ch[0]->ans;
if(ch[1]!=Null)ans^=ch[1]->ans;
}

int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}

void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y)){Rotate(x,y->ch[0]==x);}
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,1);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *ToLct(int x){
return root[x];
}

int Xor(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Makeroot(u);
Access(v);
Splay(v);
return v->ans;
}

void Add(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Link(u,v);
}

void Delete(int x,int y){
Node *u=ToLct(x),*v=ToLct(y);
Cut(u,v);
}

void Change(int x,int y){
Node *u=ToLct(x);
Access(u);
Splay(u);
u->v=y;
u->Pushup();
}

Node *GetNull(){
Node *re=new Node(0,re);
re->v=re->ans=re->rev=0;
re->ch[0]=re->fa=re->ch[1]=re;
return re;
}

int main(){
freopen("3282.in","r",stdin);
freopen("3282.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++){
	int tp;
	scanf("%d",&tp);
	root[i]=new Node(tp,Null);
}
for(int i=1;i<=m;i++){
	int opt,x,y;
    scanf("%d %d %d",&opt,&x,&y);
    if(opt==0){printf("%d\n",Xor(x,y));}
    if(opt==1 && Find(ToLct(x))!=Find(ToLct(y)) && x!=y){Add(x,y);}
    if(opt==2 && Find(ToLct(x))==Find(ToLct(y)) && x!=y){Delete(x,y);}
    if(opt==3){Change(x,y);}
}
return 0;
}

疯狂的块状链表……

我写个半成品程序放这儿坑着……不知道哪天会填坑……

感觉写到快崩溃了……

jcvb写的完整版也就我这么长……但我只写了一半……orzorz

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

struct List{
long long cur[1105],cover,rev,tag,sum,mx,mn,siz;
List *prev,*next;
List(List *pre,List *nex){
siz=0;
mx=-21000000000ll;
mn=21000000000ll;
sum=0;
rev=0;
tag=0;
cover=-21000000000ll;
prev=pre;
next=nex;
}
void Renew(long long k){
mx=max(mx,k);
mn=min(mn,k);
sum+=k;
}
void Fix(){
prev->next=this;
next->prev=this;
}
}*root,*Null=new List(Null,Null);

int m,n,block_size;
long long a[100005],tmp[1105];

void Read(long long &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

void PushTag(List *p){
if(p->tag){
	for(int i=0;i<p->siz;i++)p->cur[i]+=p->tag;
	p->tag=0;
}
}

void PushCover(List *p){
if(p->cover!=-21000000000ll){
	for(int i=0;i<p->siz;i++)p->cur[i]=p->cover;
	p->cover=-21000000000ll;
}
}

void PushRev(List *p){
if(p->rev){
	for(int i=0;i<p->siz/2;i++)swap(p->cur[i],p->cur[p->siz-i-1]);
	p->rev=0;
}
}

void Pushdown(List *p){
PushTag(p);
PushCover(p);
PushRev(p);
}

void CopyTags(List *p,List *q){
p->cover=q->cover;
p->tag=q->tag;
p->rev=q->rev;
}

List* Split(List *lis,int k){
List *p=new List(lis,lis->next);
lis->next=p;
lis->Fix();
p->Fix();
PushRev(lis);
CopyTags(p,lis);
lis->mx=-21000000000ll;
lis->mn=21000000000ll;
lis->sum=0;
for(int i=0;i<=k;i++){
	lis->Renew(lis->cur[i]);
}
lis->siz=k+1;
if(p->cover)return p;
for(int i=k+1;i<lis->siz;i++){
	p->cur[p->siz++]=lis->cur[i];
	p->Renew(lis->cur[i]);
}
return p;
}

List* Merge(List *p,List *q){
p->next=q;
q->prev=p;
p->Fix();
q->Fix();
Pushdown(p);
Pushdown(q);
for(int i=0;i<q->siz;i++){
	p->cur[p->siz++]=q->cur[i];
	p->Renew(q->cur[i]);
}
return p;
}

void Swap(List *p,List *q){
p->prev->next=q;
q->next->prev=p;
p->next->prev=q;
q->prev->next=p;
swap(p->next,q->next);
swap(p->prev,q->prev);
}

pair<List*,int> Location(int pos){
List *i;
for(i=root;i!=Null && pos>i->siz;pos-=i->siz,i=i->next);
return make_pair(i,pos-1);
}
///Wo Mei You You Hua block_size;
void Insert(int pos,long long val){
pair<List*,int> Real=Location(pos);
Real.second++;
Pushdown(Real.first);
for(int i=Real.first->siz;i>Real.second;i--){
	Real.first->cur[i]=Real.first->cur[i-1];
}
Real.first->siz++;
Real.first->cur[Real.second]=val;
Real.first->Renew(val);
if(Real.first->siz>2*block_size){Split(Real.first,Real.first->siz/2);}
}

void Delete(int pos){
pair<List*,int> Real=Location(pos);
Pushdown(Real.first);
Real.first->mx=-2100000000ll;
Real.first->mn=21000000000ll;
Real.first->sum=0;
for(int i=0;i<Real.second;i++)Real.first->Renew(Real.first->cur[i]);
for(int i=Real.second+1;i<Real.first->siz;i++){
	Real.first->Renew(Real.first->cur[i]);
	Real.first->cur[i-1]=Real.first->cur[i];
}
Real.first->siz--;
if(Real.first->siz<block_size/2){
	if(Real.first->next!=Null){Merge(Real.first,Real.first->next);}
	else {
		if(Real.first->prev!=Null){Merge(Real.first->prev,Real.first);}
	}
}
}

void Reverse(int l,int r){
pair<List*,int> R1=Location(l),R2=Location(r);
Pushdown(R1.first);
Pushdown(R2.first);
List *p=Split(R1.first,R1.second),*q=Split(R2.first,R2.second)->prev;
int flag=0;
for(List *i=p;i!=q;i=i->next){i->rev^=1;}
for(;p!=q && p!=q->next;p=p->next,q=q->prev)Swap(p,q);
}

void True_rotate(List *lis,int k){
int cnt=0,Circle=lis->siz;
for(int i=0;i<Circle;i++){
	tmp[(++cnt+k-1)%Circle+1]=lis->cur[i];
}
for(int i=0;i<Circle;i++){
	lis->cur[i]=tmp[i-k+1];
}
}

void Rotate(int l,int r,int k){
pair<List*,int> R1=Location(l),R2=Location(r);
if(R1.first==R2.first){
	List *p=Split(R1.first,R1.second-1),*q=Split(R1.first->next,R2.second-R1.second+1)->prev;
	p=Merge(p,q);
	True_rotate(p,k);
	return;
}
if(R1.first->next==R2.first){
    List *p=Split(R1.first,R1.second-1),*q=Split(R2.first,R2.second)->prev;
	p=Merge(p,q);
	True_rotate(p,k);
	return;
}

}

void Add(int l,int r,long long v){

}

void Cover(int l,int r,long long val){

}

long long Sum(int l,int r){}

long long MinAbs(int l,int r){}

long long PrevNext(int l,int r,long long val){}

long long Kth(int l,int r,int k){}

int Rank(int l,int r,long long val){}

int main(){
freopen("3337.in","r",stdin);
freopen("3337.out","w",stdout);
Read(n);
for(int i=1;i<=n;i++){
	Read(a[i]);
}
block_size=(int)sqrt((double)n);
root=new List(Null,Null);
List *p=root;
int Count=0;
for(int i=1;i<=n;i++){
if((i-1)%block_size==0 && i!=1){
	p->next=new List(p,Null);
	p->siz=Count;
	p=p->next;
	Count=0;
}
p->Renew(a[i]);
p->cur[Count++]=a[i];
}
p->siz=Count;
Read(m);
while(m--){
	int opt,l,r,k;
	long long v;
	Read(opt);
	if(opt==1){
		Read(k);Read(v);
		Insert(k,v);
	}
	if(opt==2){
		Read(k);
		Delete(k);
	}
	if(opt==3){
		Read(l);Read(r);
		Reverse(l,r);
	}
	if(opt==4){
		Read(l);Read(r);Read(k);
		Rotate(l,r,k);
	}
	if(opt==5){
		Read(l);Read(r);Read(v);
		Add(l,r,v);
	}
	if(opt==6){
		Read(l);Read(r);Read(v);
		Cover(l,r,v);
	}
	if(opt==7){
		Read(l);Read(r);
		printf("%lld\n",Sum(l,r));
	}
	if(opt==8){
		Read(l);Read(r);
		printf("%lld\n",MinAbs(l,r));
	}
	if(opt==9){
		Read(l);Read(r);Read(v);
		printf("%lld\n",PrevNext(l,r,v));
	}
	if(opt==10){
		Read(l);Read(r);Read(k);
		printf("%lld\n",Kth(l,r,k));
	}
	if(opt==11){
		Read(l);Read(r);Read(v);
		printf("%d\n",Rank(l,r,v));
	}
}
return 0;
}

Splay模版题。

虽然最近学习了fhqTreap但是还是先写个splay吧，补一补以前的漏洞……

Splay

#include<cstdio>
#include<algorithm>
using namespace std;

struct Node{
Node *ch[2],*fa;
int v,mx,tag,rev,siz;
Node(int val,Node* fa);
void Pushup();
void Pushdown();
}*root,*Null=new Node(-2100000000,Null);

int n,m;

Node::Node(int val=0,Node* fat=Null){
siz=1;
fa=fat;
ch[0]=ch[1]=Null;
v=mx=val;
tag=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
if(tag){
	if(ch[0]!=Null){ch[0]->tag+=tag;ch[0]->v+=tag;ch[0]->mx+=tag;}
	if(ch[1]!=Null){ch[1]->tag+=tag;ch[1]->v+=tag;ch[1]->mx+=tag;}
	tag=0;
}
}

void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
mx=v;
if(ch[0]!=Null)mx=max(mx,ch[0]->mx);
if(ch[1]!=Null)mx=max(mx,ch[1]->mx);
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place){Rotate(x,y->ch[0]==x);}
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,1);Rotate(x,0);}
	}
}
if(place==Null)root=x;
}

Node* Build_Tree(int l,int r){
int mid=l+r>>1;
if(l>r)return Null;
Node *splay=new Node(0,Null);
splay->ch[0]=Build_Tree(l,mid-1);
if(splay->ch[0]!=Null){splay->ch[0]->fa=splay;}
splay->ch[1]=Build_Tree(mid+1,r);
if(splay->ch[1]!=Null){splay->ch[1]->fa=splay;}
splay->Pushup();
return splay;
}

void Build(){
Null->siz=0;
root=new Node(-2100000000,Null);
root->ch[1]=new Node(-2100000000,root);
root->ch[1]->fa=root;
root->ch[1]->ch[0]=Build_Tree(1,n);
root->ch[1]->ch[0]->fa=root->ch[1];
root->ch[1]->Pushup();
root->Pushup();
}

Node *Find(Node *splay,int k){
if(splay->rev || splay->tag)splay->Pushdown();
if(k==splay->ch[0]->siz+1){return splay;}
if(k<=splay->ch[0]->siz){return Find(splay->ch[0],k);}
else {return Find(splay->ch[1],k-1-splay->ch[0]->siz);}
}

Node *GetSeq(int l,int r){
Node *L=Find(root,l);
Splay(L,Null);
Node *R=Find(root,r+2);
Splay(R,root);
return R->ch[0];
}

void Reverse(int l,int r){
Node *seq=GetSeq(l,r);
seq->rev^=1;
}

void Add(int l,int r,int val){
Node *seq=GetSeq(l,r);
seq->tag+=val;
seq->v+=val;
seq->mx+=val;
}

int GetMx(int l,int r){
Node *seq=GetSeq(l,r);
return seq->mx;
}

int main(){
freopen("1251.in","r",stdin);
freopen("1251.out","w",stdout);
scanf("%d %d",&n,&m);
Build();
while(m--){
	int opt,l,r,v;
	scanf("%d",&opt);
	if(opt==1){scanf("%d %d %d",&l,&r,&v);Add(l,r,v);}
	if(opt==2){scanf("%d %d",&l,&r);Reverse(l,r);}
	if(opt==3){scanf("%d %d",&l,&r);printf("%d\n",GetMx(l,r));}
}
return 0;
}

fhqTreap(待填坑)

bzoj上的坑题……

数组要放大，必须开long long

#include<cstdio>
#include<algorithm>
using namespace std;

struct Go{
long long add,dec,rev;
long long i;
friend bool operator<(Go a,Go b){
	if(a.rev>=0 && b.rev>=0){return a.dec<b.dec;}
	if(a.rev<0 && b.rev<0){return a.add>b.add;}
	if(a.rev>=0 && b.rev<0)return 1;
	if(a.rev<0 && b.rev>=0)return 0;
}
}da[1000005];

long long n,z;

int main(){
freopen("3709.in","r",stdin);
freopen("3709.out","w",stdout);
scanf("%lld %lld",&n,&z);
for(long long i=1;i<=n;i++)scanf("%lld %lld",&da[i].dec,&da[i].add),da[i].rev=da[i].add-da[i].dec,da[i].i=i;
sort(da+1,da+1+n);
for(long long i=1;i<=n;i++){
	z-=da[i].dec;
	if(z<=0){puts("NIE");return 0;}
	z+=da[i].add;
}
puts("TAK");
for(long long i=1;i<=n;i++)printf("%lld ",da[i].i);
return 0;
}

暴力。。

#include<cstdio>

int n,cir[25],sum[25],ans=0;

int main(){
freopen("1800.in","r",stdin);
freopen("1800.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&cir[i]);sum[i]=cir[i]+sum[i-1];}
for(int i=1;i<=n;i++){
	for(int j=i+1;j<=n;j++){
		for(int k=j+1;k<=n;k++){
			for(int l=k+1;l<=n;l++){
				if(sum[j-1]-sum[i-1]==sum[l-1]-sum[k-1] && sum[k-1]-sum[j-1]==sum[n]-sum[l-1]+sum[i-1])ans++;
			}
		}
	}
}
printf("%d\n",ans);
return 0;
}

第一次写分块，挑了这题写……

然后调了一个晚上。

各种猎奇的错误都被我犯了……

人傻就是要多做题。

分块+二分

参考hzwer的

弱智错误记录:

1.数组要注意清空:这个在WC2016上已经让我的T1 60->0了……以后要认真吸取教训

2.不要乱开局部数组:这样会显著增大常数

3.要知道自己二分的是什么，不要搞着搞着就搞乱了

以上

Claris也在坚持刷题……太可怕了，本身实力超强还在刷……orzzzz

#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

int n,c,m,a[100005],f[1505][1505],fir[100005],las[100005],block,ans=0,L[1505],R[1505],belong[100005],tmp[100005],cnt;

struct Data{
int a,b;
friend bool operator<(Data a,Data b){
return (a.a<b.a)||(a.a==b.a && a.b<b.b);
}
}data[100005];

pair<int,int> GetLR(int L,int R){
L=(L+ans)%n+1;
R=(R+ans)%n+1;
if(L>R)swap(L,R);
return make_pair(L,R);
}

void Pre(){
for(int i=1;i<=cnt;i++){
	for(int j=L[i];j<=n;j++)tmp[a[j]]=0;
	int tot=0;
	for(int j=L[i];j<=n;j++){
		if(tmp[a[j]]%2==0 && tmp[a[j]])tot--;
		tmp[a[j]]++;
		if(tmp[a[j]]%2==0)tot++;
		f[i][belong[j]]=tot;
	}
}
//for(int i=belong[1];i<=belong[n];i++){for(int j=i;j<=belong[n];j++){printf("%d ",f[i][j]);}putchar('\n');}
for(int i=1;i<=n;i++)data[i].a=a[i],data[i].b=i;
sort(data+1,data+n+1);
for(int i=1;i<=n;i++){
	if(fir[data[i].a]==0)fir[data[i].a]=i;
	las[data[i].a]=i ;
}
}

int Ef_Fir(int x,int v){
int tp=214748364,l=fir[v],r=las[v];
while(l<=r){
	int mid=l+r>>1;
	if(x>data[mid].b)l=mid+1;
	else {r=mid-1;tp=mid;}
}
return tp;
}

int Ef_Las(int x,int v){
int tp=0,l=fir[v],r=las[v];
while(l<=r){
	int mid=l+r>>1;
	if(x<data[mid].b)r=mid-1;
	else {l=mid+1;tp=mid;}
}
return tp;
}

int Ef(int x,int y,int v){
//printf("%d %d %d | EF:%d %d\n",x,y,v,Ef_Las(y,v),Ef_Fir(x,v));
return max(Ef_Las(y,v)-Ef_Fir(x,v)+1,0);
}

int solve(int l,int r){
//printf("LR:%d %d\n",l,r);
int nwans=0,kl=belong[l],kr=belong[r];
if(kl+1==kr || kl==kr){
	for(int i=l;i<=r;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]);
		if(sp%2==0){nwans++;}
		//printf("%d %d %d\n",l,r,a[i]);
		tmp[a[i]]=1;
	}
	for(int i=l;i<=r;i++)tmp[a[i]]=0;
	return nwans;
}
else {
    int fs=L[kl+1],la=R[kr-1];
    nwans=f[kl+1][kr-1];
    //printf("%d %d | NW_ANS1:%d\n",kl,kr,nwans);
    for(int i=l;i<fs;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
		if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
		if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
		//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
		tmp[a[i]]=1;
    }
    //printf("NW_ANS2:%d\n",nwans);
    for(int i=la+1;i<=r;i++){
		if(tmp[a[i]])continue;
		int sp=Ef(l,r,a[i]),sp2=Ef(fs,la,a[i]);
		if(sp2%2==0 && sp%2 && sp2!=0){nwans--;}
		if((sp2%2 || sp2==0) && sp%2==0){nwans++;}
		//printf("SP:%d SP2:%d_%d_",sp,sp2,nwans);
		tmp[a[i]]=1;
    }
    for(int i=l;i<fs;i++)tmp[a[i]]=0;
    for(int i=la+1;i<=r;i++)tmp[a[i]]=0;
    return nwans;
}
}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("2821.in","r",stdin);
freopen("2821.out","w",stdout);
Read(n);Read(c);Read(m);
for(int i=1;i<=n;i++){
	Read(a[i]);
}
block=(int)sqrt((double)n/log(n)*log(2));
cnt=n/block+(n%block!=0);
for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
for(int i=1;i<=cnt;i++)L[i]=R[i-1]+1,R[i]=i*block;
R[cnt]=n;
Pre();
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=m;i++){
	int tl,tr;
	Read(tl);Read(tr);
    pair<int,int> Ask=GetLR(tl,tr);
    //pair<int,int> Ask=make_pair(tl,tr);
    ans=solve(Ask.first,Ask.second);
    printf("%d\n",ans);
}
return 0;
}

CDQ分治

递归处理左边的操作，再计算影响，然后处理右边的操作。

使用一个树状数组，利用排序x坐标的单调性，然后直接在树状数组上操作就行了。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
struct Do{
int flag,x,y,id,v,pos;
friend bool operator <(const Do &a,const Do &b){
return a.x==b.x?(a.y==b.y?a.pos<b.pos:a.y<b.y):a.x<b.x;
}
}Q[200005],tmp[200005];
 
int s,w,tot,_Y[210005],toty,ans[10005],totans,BIT[200005],t1,t2,cnt;
 
int lowbit(int x){
return x&(-x);
}
 
void Add(int pos,int val){
while(pos<=toty){
    BIT[pos]+=val;
    pos+=lowbit(pos);
}
}
 
int Query(int pos){
int ans=0;
while(pos){
    ans+=BIT[pos];
    pos-=lowbit(pos);
}
return ans;
}
 
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1,t1=l,t2=mid+1;
for(int i=l;i<=r;i++){
    //printf("Hello!:%d %d %d %d %d\n",Q[i].id,mid,Q[i].flag,Q[i].fg,Q[i].pos);
    if(Q[i].id<=mid && Q[i].flag==1){Add(Q[i].y,Q[i].v);/*printf("Reggle:%d %d\n",Query(Q[i].y),Q[i].v);*/}
    if(Q[i].id>mid && Q[i].flag==2){/*puts("233");printf("Leggle:%d\n",Query(Q[i].y));*/ans[Q[i].pos]+=Q[i].v*Query(Q[i].y);}
}
for(int i=l;i<=r;i++){
    if(Q[i].id<=mid && Q[i].flag==1)Add(Q[i].y,-Q[i].v);
}
for(int i=l;i<=r;i++){
    if(Q[i].id<=mid)tmp[t1++]=Q[i];
    else tmp[t2++]=Q[i];
}
for(int i=l;i<=r;i++){
    Q[i]=tmp[i];
}
CDQ(l,mid);
CDQ(mid+1,r);
}
 
int main(){
freopen("1176.in","r",stdin);
freopen("1176.out","w",stdout);
scanf("%d %d",&s,&w);
while(scanf("%d",&Q[++tot].flag)!=EOF){
    if(Q[tot].flag==3){tot--;break;}
    if(Q[tot].flag==1){
        scanf("%d %d %d",&Q[tot].x,&Q[tot].y,&Q[tot].v);
        _Y[++toty]=Q[tot].y;
        Q[tot].id=tot;
        Q[tot].pos=0;
    }
    else {
        int x1,x2,y1,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        ans[++cnt]=s*(x2-x1+1)*(y2-y1+1);
        Q[tot].x=x1-1;
        Q[tot].y=y1-1;
        Q[tot].id=tot;
        Q[tot].pos=cnt;
        Q[tot].v=1;
        _Y[++toty]=Q[tot].y;
        tot++;
        Q[tot].flag=2;
        Q[tot].x=x2;
        Q[tot].y=y1-1;
        Q[tot].id=tot;
        Q[tot].pos=cnt;
        Q[tot].v=-1;
        tot++;
        Q[tot].flag=2;
        Q[tot].x=x1-1;
        Q[tot].y=y2;
        Q[tot].id=tot;
        _Y[++toty]=Q[tot].y;
        Q[tot].pos=cnt;
        Q[tot].v=-1;
        tot++;
        Q[tot].flag=2;
        Q[tot].x=x2;
        Q[tot].y=y2;
        Q[tot].pos=cnt;
        Q[tot].id=tot;
        Q[tot].v=1;
    }
}
sort(_Y+1,_Y+toty+1);
toty=unique(_Y+1,_Y+toty+1)-_Y-1;
for(int i=1;i<=tot;i++){
    Q[i].y=lower_bound(_Y+1,_Y+toty+1,Q[i].y)-_Y;
}
sort(Q+1,Q+tot+1);
CDQ(1,tot);
for(int i=1;i<=cnt;i++){
    printf("%d\n",ans[i]);
}
return 0;
}

CLJ的题目真是猛……我调了一个晚上……才发现是开始的排序出了问题……真是……人弱没办法……

二分+可持久化线段树。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,Q,a[20005],b[20005],m,root[20005],cnt,ms[4],ans;
pair<int,int> s[20005];

struct SegTree{
int nl,nr,cnt,lx,rx;
}tree[1000005];

void OutNode(SegTree d){
puts("\nThis is a SegTree Node:");
printf("nl:%d nr:%d cnt:%d lx:%d rx:%d\n\n",d.nl,d.nr,d.cnt,d.lx,d.rx);
}

void OutTree(int l,int r,int root){
printf("%d %d The Tree:%d %d %d\n",l,r,tree[root].lx,tree[root].cnt,tree[root].rx);
if(l==r)return;
int mid=l+r>>1;
OutTree(l,mid,tree[root].nl);
OutTree(mid+1,r,tree[root].nr);
}

void Pushup(int root){
tree[root].lx=max(tree[tree[root].nl].lx,tree[tree[root].nl].cnt+tree[tree[root].nr].lx);
tree[root].rx=max(tree[tree[root].nr].rx,tree[tree[root].nr].cnt+tree[tree[root].nl].rx);
tree[root].cnt=tree[tree[root].nl].cnt+tree[tree[root].nr].cnt;
}

void Build(int l,int r,int &root){
root=++cnt;
if(l==r){
    tree[root].lx=1;
    tree[root].rx=1;
    tree[root].cnt=1;
    tree[root].nl=0;
    tree[root].nr=0;
    //printf("--------------------L:%d\n",l);
    return;
}
int mid=l+r>>1;
Build(l,mid,tree[root].nl);
Build(mid+1,r,tree[root].nr);
Pushup(root);
return;
}

void Update(int l,int r,int &root,int lastroot,int pos){
root=++cnt;
tree[root].nl=tree[lastroot].nl;
tree[root].nr=tree[lastroot].nr;
if(l==r){
    tree[root].cnt=-1;
    tree[root].lx=-1;
    tree[root].rx=-1;
    //printf("----------------------R:%d\n",tree[root].rx);
    return;
}
int mid=l+r>>1;
if(pos<=mid)Update(l,mid,tree[root].nl,tree[lastroot].nl,pos);
else Update(mid+1,r,tree[root].nr,tree[lastroot].nr,pos);
Pushup(root);
}

SegTree Ask(int root,int l,int r,int L,int R){
if(l>r)return tree[0];
if(L>=l && R<=r)return tree[root];
int mid=L+R>>1;
SegTree a=tree[0],b=tree[0];
if(l>mid)return Ask(tree[root].nr,l,r,mid+1,R);
if(r<=mid)return Ask(tree[root].nl,l,r,L,mid);
a=Ask(tree[root].nl,l,r,L,mid);
b=Ask(tree[root].nr,l,r,mid+1,R);
SegTree c;
c.lx=max(a.lx,a.cnt+b.lx);
c.rx=max(b.rx,b.cnt+a.rx);
c.cnt=a.cnt+b.cnt;
//OutNode(c);
return c;
}

int Query(){
int l=1,r=n+1,Ans=0;
while(l<r){
    int mid=l+r>>1;
    SegTree a=Ask(root[mid],ms[0],ms[1],1,m),b=Ask(root[mid],ms[1]+1,ms[2]-1,1,m),c=Ask(root[mid],ms[2],ms[3],1,m);
    //OutTree(1,n,root[mid]);
    //printf("MID:%d %d %d %d %d\n",mid,root[mid],a.rx,b.cnt,c.lx);
    int sum=a.rx+b.cnt+c.lx;
    if(sum>=0)l=mid+1,Ans=mid;
    else r=mid;
}
return Ans;
}

int main(){
//freopen("2653.in","r",stdin);
//freopen("2653.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    b[i]=a[i];
}
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+m+1,a[i])-b;s[i].first=a[i];s[i].second=i;/*printf("Ai:%d\n",a[i]);*/}
sort(s+1,s+n+1);
//for(int i=1;i<=n;i++)printf("Si:%d\n",s[i].second);
Build(1,m,root[1]);
for(int i=2;i<=n;i++)Update(1,m,root[i],root[i-1],s[i-1].second);
scanf("%d",&Q);
while(Q--){
    scanf("%d %d %d %d",&ms[0],&ms[1],&ms[2],&ms[3]);
    ms[0]=(ms[0]+ans)%n+1;
    ms[1]=(ms[1]+ans)%n+1;
    ms[2]=(ms[2]+ans)%n+1;
    ms[3]=(ms[3]+ans)%n+1;
    sort(ms,ms+4);
    //printf("MS:%d %d %d %d\n",ms[0],ms[1],ms[2],ms[3]);
    ans=b[Query()];
    //printf("QUERY:%d\n",Query());
    printf("%d\n",ans);
}
return 0;
}

很久没更新了呢。

这题我写的是可持久化线段树版本的。

代码参考了hzwer的，orzzzzzzzzzzzz

#include<cstdio>
#include<algorithm>
using namespace std;

long long n,m,h[100005],root[100005],en,lca[100005][20],a[100005],b[100005],deep[100005],es,dfn[100005],pos[100005],dfscnt,cnt,ans=0;

struct Edge{
long long b,next;
}e[200005];

struct SegTree{
long long nl,nr,v;
}tree[3000005];

void Add(long long sa,long long sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

long long LCA(long long u,long long v){
if(deep[u]<deep[v])swap(u,v);
long long sou=deep[u]-deep[v];
for(long long i=0;i<=18;i++)if((1<<i)&sou)u=lca[u][i];
for(long long i=18;i>=0;i--)if(lca[u][i]!=lca[v][i]){u=lca[u][i];v=lca[v][i];}
if(u==v)return u;
return lca[u][0];
}

void DFS(long long u){
dfn[++dfscnt]=u;
pos[u]=dfscnt;
for(long long i=1;i<=18;i++){
    if((1<<i)<=deep[u])lca[u][i]=lca[lca[u][i-1]][i-1];
    else break;
}
for(long long i=h[u];i;i=e[i].next){
    long long v=e[i].b;
    if(lca[u][0]!=v){
        deep[v]=deep[u]+1;
        lca[v][0]=u;
        DFS(v);
    }
}
}

long long Query(long long a,long long bs,long long c){
long long Lca=LCA(a,bs);
//printf("ABCD:%lld %lld %lld %lld\n",pos[a],pos[bs],pos[Lca],pos[lca[Lca][0]]);
long long sa=root[pos[a]],sb=root[pos[bs]],sc=root[pos[Lca]],sd=root[pos[lca[Lca][0]]];
long long l=1,r=es;
while(l<r){
    long long mid=l+r>>1,Sum=tree[tree[sa].nl].v+tree[tree[sb].nl].v-tree[tree[sc].nl].v-tree[tree[sd].nl].v;
    //printf("SUM:%lld\n",Sum);
    if(Sum>=c){r=mid;sa=tree[sa].nl;sb=tree[sb].nl;sc=tree[sc].nl;sd=tree[sd].nl;}
    else {c-=Sum;l=mid+1;sa=tree[sa].nr;sb=tree[sb].nr;sc=tree[sc].nr;sd=tree[sd].nr;}
}
return b[l];
}

void Update(long long l,long long r,long long &root,long long lastroot,long long pos){
root=++cnt;
tree[root].v=tree[lastroot].v+1;
if(l==r)return;
tree[root].nl=tree[lastroot].nl;
tree[root].nr=tree[lastroot].nr;
long long mid=l+r>>1;
if(pos<=mid)Update(l,mid,tree[root].nl,tree[lastroot].nl,pos);
else Update(mid+1,r,tree[root].nr,tree[lastroot].nr,pos);
}

int main(){
freopen("2588.in","r",stdin);
freopen("2588.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(long long i=1;i<=n;i++){
    scanf("%lld",&a[i]);
    b[i]=a[i];
}
sort(b+1,b+n+1);
es=unique(b+1,b+1+n)-b-1;
for(long long i=1;i<=n;i++)a[i]=lower_bound(b+1,b+es+1,a[i])-b;
for(long long i=1;i<n;i++){
    long long sa,sb;
    scanf("%lld %lld",&sa,&sb);
    Add(sa,sb);
    Add(sb,sa);
}
DFS(1);
for(long long i=1;i<=n;i++){
    //printf("ROT:%lld\n",root[pos[lca[dfn[i]][0]]]);
    Update(1,es,root[i],root[pos[lca[dfn[i]][0]]],a[dfn[i]]);
}
for(long long i=1;i<=m;i++){
    long long a,b,c;
    scanf("%lld %lld %lld",&a,&b,&c);
    a^=ans;
    ans=Query(a,b,c);
    if(i!=m)printf("%lld\n",ans);
    else printf("%lld",ans);
}
return 0;
}

明显是一个最大流啊……

坑明天填上……

今天是2016年7月31日，我仍然没有填这个坑。

所以，我力争在三天内填好所有的坑(flag)，谢谢各位看我博客的神犇……

长期未填坑表示抱歉……

----------------

说好的填坑来了

我一开始以为是曼哈顿距离，错了好久……

拆点，两点间流量为两点间高度，然后考虑建超级源点连向每个有蜥蜴的柱子上面容量1

所有能跳出的柱子下面向超级汇点连接容量INF

没了

为什么？把蜥蜴看成1的流量模拟一下即可

下面程序中bfs_add为曼哈顿距离的建图

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=1005,INF=2100000000;

int r,c,d,h[N],en,level[N],S,T,cur[N],t[25][25],rex,p[N][N];
char mp[N][N];
queue<int> Q;
queue<pair<pair<int,int>,int> > Qx;

struct Edge{
int b,f,next,back;
}e[N*100];

inline int GetID(int x,int y){return (x-1)*c+y;}

inline void AddEdge(int sa,int sb,int sc){
//printf("Line %d %d %d\n",sa,sb,sc);
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}

inline int bfs(){
memset(level,0,sizeof(level));
Q.push(S);level[S]=1;
while(!Q.empty()){
	int u=Q.front();Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		if(e[i].f && !level[v])level[v]=level[u]+1,Q.push(v);
	}
}
return level[T];
}

int dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
	int fl,v=e[i].b;
	if(level[v]==level[u]+1 && e[i].f && (fl=dfs(v,min(f,e[i].f)))){
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		f-=fl;
		if(!f)return flow;
	}
}
return flow-f;
}

inline int Dinic(){
int ans=0;
while(bfs()){
	for(int i=1;i<=T;i++)cur[i]=h[i];
	ans+=dfs(S,INF);
}
return ans;
}

inline int Abs(const int &x){return x>0?x:-x;}
inline int Dist(const int &x1,const int &y1,const int &x2,const int &y2){return Abs(x2-x1)+Abs(y2-y1);}

/*inline void bfs_add(const int &x,const int &y){
int id=GetID(x,y);
memset(t,0,sizeof(t));
t[x][y]=1;
Qx.push(make_pair(make_pair(x+1,y),d-1));
Qx.push(make_pair(make_pair(x,y+1),d-1));
Qx.push(make_pair(make_pair(x-1,y),d-1));
Qx.push(make_pair(make_pair(x,y-1),d-1));
while(!Qx.empty()){
	pair<pair<int,int>,int> Px=Qx.front();Qx.pop();
	if(Px.first.first<1 || Px.first.first>r || Px.first.second<1 || Px.first.second>c)Px.first.first=0,Px.first.second=0;
	if(t[Px.first.first][Px.first.second])continue;
	t[Px.first.first][Px.first.second]=1;
	//printf("T:%d %d\n",Px.first.first,Px.first.second);
	if(Px.first.first==0 && Px.first.second==0){AddEdge(id+r*c,T,INF);continue;}
	if(p[Px.first.first][Px.first.second])AddEdge(id+r*c,GetID(Px.first.first,Px.first.second),INF);
	if(Px.second==0)continue;
    Qx.push(make_pair(make_pair(Px.first.first+1,Px.first.second),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first,Px.first.second+1),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first-1,Px.first.second),Px.second-1));
    Qx.push(make_pair(make_pair(Px.first.first,Px.first.second-1),Px.second-1));
}
}*/

inline void Build(){
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(!p[i][j])continue;
		if(i-d<1 || i+d>r || j-d<1 || j+d>c)AddEdge(GetID(i,j)+r*c,T,INF);
		for(int i1=1;i1<=r;i1++){
			for(int j1=1;j1<=c;j1++){
				if(!p[i1][j1] || (i==i1 && j==j1))continue;
				if((i1-i)*(i1-i)+(j1-j)*(j1-j)<=d*d)AddEdge(GetID(i,j)+r*c,GetID(i1,j1),INF);
			}
		}
	}
}
}

int main(){
freopen("1066.in","r",stdin);
freopen("1066.out","w",stdout);
scanf("%d %d %d",&r,&c,&d);
S=2*r*c+1;T=S+1;
for(int i=1;i<=r;i++)scanf("%s",mp[i]+1);
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++)if(mp[i][j]>'0')p[i][j]=1;
}
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(p[i][j]){
			int id=GetID(i,j);
			AddEdge(id,r*c+id,mp[i][j]-'0');
			//bfs_add(i,j);
		}
	}
}
Build();
//printf("S:%d T:%d\n",S,T);
for(int i=1;i<=r;i++)scanf("%s",mp[i]+1);
for(int i=1;i<=r;i++){
	for(int j=1;j<=c;j++){
		if(mp[i][j]=='L')AddEdge(S,GetID(i,j),1),rex++;
	}
}
printf("%d\n",rex-Dinic());
return 0;
}