BZOJ2819: Nim【树状数组+dfs序+倍增求LCA】

树上的Nim取石子游戏。

说白了就是，维护一棵树，支持：修改点权，询问一条路径上点权的xor值是否为零。

可以用树链剖分做。但是介于n和q都50w这么大感觉常数很DT。。

既然它只修改点的话，影响到的只是它这棵子树。那么很容易就想到了dfs序。这个子树就是连续一段。

先维护每个点dfs开始时和结束时的时间戳。修改的时候先在它自己的开始、结束位置上xor它自己变成零，然后再修改。

(x,y)路径上的xor值=query(x的开始) xor query(y的开始) xor lca(x,y)的点权。很好想通。LCA就倍增算一下好了。

没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define YES *o++='Y',*o++='e',*o++='s',*o++='\n'
#define NO *o++='N',*o++='o',*o++='\n'
const int maxn=500100,maxm=1000100;
int p[maxm],n1[maxm],h[maxn],begin[maxn],end[maxn],bit[maxm],st[maxn],a[maxn],n,ee=0,tot=0;
int anc[maxn][20],dep[maxn];	char buf[25000000],*o=buf,*pt=buf;
inline int getint(){
    int s=0;	while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; 
	return s;
}inline char getop(){
	while(*pt!='Q'&&*pt!='C')	pt++;	return *pt++;
}inline void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
	p[ee]=a;	n1[ee]=h[b];	h[b]=ee++;
}inline void dfs(int s){
	int top=0;
	begin[st[++top]=s]=dep[s]=++tot;
	while(top){
		int u=st[top],f=0;
		for(int i=h[u];~i;i=n1[i]){
			if(!~begin[p[i]]){
				begin[p[i]]=++tot;
				anc[p[i]][0]=u;
				dep[p[i]]=dep[u]+1;
				st[++top]=p[i];
				h[u]=n1[i];
				f=1;
				break;
			}
		}if(!f){
			end[u]=++tot;
			top--;
		}
	}
}inline int lca(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	int k=dep[u]-dep[v],j=0;
	while(k){
		if(k&1)	u=anc[u][j];
		j++,k>>=1;
	}if(u==v)	return u;
	for(int j=19;~j;j--)
		if(anc[u][j]!=anc[v][j])	u=anc[u][j],v=anc[v][j];
	return anc[u][0];
}inline void modify(int i){
	for(int x=begin[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
	for(int x=end[i];x<maxm;x+=x&-x)	bit[x]^=a[i];
}inline int ask(int x){
	int r=0;
	for(;x;x-=x&-x)	r^=bit[x];
	return r;
}int main(){
	fread(buf,1,25000000,stdin);
	n=getint();
	for(int i=1;i<=n;i++)	a[i]=getint();
	memset(h,-1,sizeof(h));
	memset(begin,-1,sizeof(begin));
	for(int i=1;i<n;i++)	ae(getint(),getint());
	dfs(1);
	for(int i=1;i<=n;i++)	modify(i);
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	int q=getint(),x,y,z;
	while(q--){
		if(getop()=='Q'){
			x=getint();y=getint();
			if(ask(begin[x])^ask(begin[y])^a[lca(x,y)])	YES;
			else	NO;
		}else{
			x=getint();y=getint();
			modify(x);
			a[x]=y;
			modify(x);
		}
	}return fwrite(buf,1,o-buf,stdout),0;
}

BZOJ 树状数组 LCA bzoj 倍增 Nim DFS序 Comments(0) 2013年8月19日 18:53

BSOJ3686 -- 【USACO 2011 November Gold】Above the Median【树状数组统计】

 

Description

Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height H_i (1 <= H_i <= 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair. 

The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000).

For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.

Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.

Input

* Line 1: Two space-separated integers: N and X.
* Lines 2..N+1: Line i+1 contains the single integer H_i.

Output

* Line 1: The number of subsequences of FJ's cows that have median at least X. Note this may not fit into a 32-bit integer.

Sample Input

4 6
10
5
6
2

INPUT DETAILS:

FJ's four cows have heights 10, 5, 6, 2. We want to know how many contiguous subsequences have median at least 6.

Sample Output

7

OUTPUT DETAILS:

There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

题意：统计有几个连续子段的中位数（A[1..k]从大到小排序后A[k/2向上取整]）大于等于给定值m。

 

应该还是比较好搞的。

把大于等于m的标记为1。小于m的标记为-1。

我们就只需要统计连续子段和非负的个数。

树状数组搞即可。

（新本本好好用。呵呵呵。）

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210000,d=100010;
int n,m,a[100010],bit[maxn+10]; 
void modify(int x){
	for(;x<=maxn;x+=x&-x)	bit[x]++;
}
int ask(int x){
	int r=0;
	for(;x;x-=x&-x)	r+=bit[x];
	return r;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>=m)	a[i]=1;	else a[i]=-1;
	}
	int sum=0;
	long long An=0;
	modify(d);
	for(int i=1;i<=n;i++){
		sum+=a[i];
		An+=1ll*ask(sum+d);
		modify(sum+d);
	}
	cout << An << endl;
	return 0;
}

 

 

BSOJ usaco 树状数组 Comments(3) 2013年8月07日 20:24

BZOJ1935: [Shoi2007]Tree 园丁的烦恼【树状数组+离散化】

题意：给定n个点，m个询问。每次询问一个矩形内有几个点。坐标范围10^7。

 

一眼看上去就很水啊。。坐标肯定是要离散化的。。询问跟着一起离散化。。然后以y为第一关键字，x为第二关键字排序。树状数组统计每个点左下角有多少个点。然后加加减减。。

离散化的细节貌似很恶心。。调着调着就A了。。

 

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

char buf[20000000],*pt=buf,*o=buf;

inline int getint(){
    int s=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++;
    if(*pt=='-')f=-1,pt++; while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s*f;
}
inline void print(int x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}

struct point{
    int x,y,id;
    point(){
        id = -1;
    };
    point(int _x,int _y,int _id){
        x = _x, y = _y, id = _id;
    }
}p[2800010];

bool cmp(point a,point b){
    if(a.y == b.y){
        if(a.x == b.x)  return a.id < b.id;
        else    return a.x < b.x;
    }
    return a.y < b.y;
}

int n,m,N,P,pc = 0;
int X[810000],Y[810000],bx[810000],by[810000],bit[2800000],cnt[2800000];

void upd(int x){
    for(;x <= N;x += x & -x)    bit[x] ++;
}
int query(int x){
    int r = 0;
    for(;x;x -= x & -x) r += bit[x];
    return r;
}

int main(){
    fread(buf,1,20000000,stdin);
    n = getint(); m = getint();
    bx[0] = by[0] = 0;
    N = n + 1;
    P = (m << 2) + n;
    bx[N] = by[N] = 12345678;
    
    for(int i = 1;i <= n;i ++){
        X[i] = getint();
        Y[i] = getint();
        bx[i] = ++ X[i];  
        by[i] = ++ Y[i];
    }
    sort(bx + 1, bx + n + 1);
    sort(by + 1, by + n + 1);
    int cx = unique(bx , bx + n + 2) - bx -1;
    int cy = unique(by , by + n + 2) - by -1;
    for(int i = 1;i <= n;i ++){
        p[(m << 2) + i - 1].x = upper_bound(bx,bx + cx,X[i]) - bx;
        p[(m << 2) + i - 1].y = upper_bound(by,by + cy,Y[i]) - by;
    }
    int x1,y1,x2,y2,X1,X2,X3,Y1,Y2,Y3;
    for(int i = 1;i <= m;i ++){
        x1=  getint(); y1=getint();x2=getint();y2=getint();
        X1 = upper_bound(bx,bx + cx,x1) - bx;
        X2 = upper_bound(bx,bx + cx,x2) - bx;
        X3 = upper_bound(bx,bx + cx,x2 + 1) - bx;
        Y1 = upper_bound(by,by + cy,y1) - by;
        Y2 = upper_bound(by,by + cy,y2) - by;
        Y3 = upper_bound(by,by + cy,y2 + 1) - by;
        p[pc] = point(X3,Y3,pc ++);
        p[pc] = point(X1,Y3,pc ++);
        p[pc] = point(X3,Y1,pc ++);
        p[pc] = point(X1,Y1,pc ++);
    }
    
    sort(p,p + P,cmp);
    for(int i = 0;i < P;i ++){
        if(~ p[i].id)   cnt[p[i].id] = query(p[i].x);
        else    upd(p[i].x);
    }
    
    for(int i = 1;i <= m;i ++)
       print(cnt[i - 1 << 2] - cnt[(i - 1 << 2) + 1] - cnt[(i - 1 << 2) + 2] + cnt[(i - 1 << 2) + 3]),*o++='\n';
        
    return fwrite(buf,1,o-buf,stdout),0;
}

BZOJ BZOJ 树状数组 离散化 Comments(1) 2013年7月30日 16:42

BZOJ2762: [JLOI2011]不等式组【树状数组+分类讨论】

分类讨论大丈夫！！！WTF！！！

题意：

1.给你不等式ax>b

2.删除第i条插入的不等式

3.询问x=k时，满足多少个给定的不等式。

n的范围10w，k的绝对值范围是100w。

那么我们可以先解出这个不等式，把符合这个不等式的所有数所在的位置加一。

比如解出来x>1，就把2~100w全都加一。x<1，就把-100w~0全都加一。

那么明显就是修改区间，单点询问。可以用线段树很好的完成。

但是不知道为什么看到100w就后怕写线段树要玩常数。于是选择了树状数组。

用树状数组的话就需要差分。比如[l,r]都加一，那么在l的位置上加一，r+1的位置上减一。这个很基础。

负数的话下标怎么办呢？设置一个偏移量d=100w+1。修改第x个时，在第x+d个位置上修改。保证下标都是正的方便操作。

看来这道题已经没什么问题了。那我们去写写看？好的。

【以下为吐槽，看tips请跳过若干个自然段】

【四天前】树状数组两行秒。ax>b自以为是的除一除就算解好了。样例很快就过了。很自信的交上去。RE还是WA来着。。然后手忙脚乱改一改还是WA。。这个时候想到了对拍。网上搞了个标程拍一拍。。不拍不知道一拍吓一跳。。然后我就被拍扁重建了。（这是替罪羊树？

发现我解ax>b的方法很不科学。感觉都没考虑全。后来直接去玩double。结果精度萎出翔。。

然后我cave in了。。

【今天】上课的时候我重新想了想ax>b该怎么解。考虑a、b的正负，发现四种情况都列出来。四个if即可。最前面再特判一下a=0就没问题了。回来信心满满的写。

造了组大数据对拍过了。很高心。结果还是WA。真是要吐血。后来突然想到，万一它要删除已经删除掉的呢。那我不就挂了吗。于是我再开了个数组记录。这回，过了。。。。。

【吐槽完了】

几个tips：

1.a=0要特判

2.ax>b分四种情况讨论（我是这么做的保险，或者有更神的方法，可惜我不会

3.如果x解出来不在-100w~100w之间要特判

4.删除已经删除的不等式直接continue！！！

贴代码。本人放个r1的代码攒rp好了~





#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int d=1000001,n=2000001,r=1000000;
int bit[n+3],A[100005],B[100005],del[100005]={0};
char op,buf[5000000],*p=buf,*o=buf;
inline void upd(int x,int d){ for(;x<=n;x+=x&-x) bit[x]+=d;}
inline int qry(int x){ int s=0; for(;x;x-=x&-x) s+=bit[x]; return s;}
inline int getint(){ int s=0,f=1; while((*p!='-')&&(*p<'0'||*p>'9'))p++;
    if(*p=='-')f=-1,p++; while(*p>='0'&&*p<='9')s=s*10+*p++-48; return s*f;
}inline char getop(){
    while(*p!='Q'&&*p!='A'&&*p!='D')p++; return *p++;
}inline void print(int x){
    char str[30],*pt=str; if(!x)*o++=48;
    else{ while(x) *pt++=x%10+48,x/=10; while(pt--!=str)*o++=*pt;}
}int main(){
    fread(p,1,5000000,stdin);
    int q,a,b,k,i=0,t1,t2,An; q=getint();
    for(int qq=1;qq<=q;qq++){
        op=getop();
        if(op=='A'){
            a=getint(),t1=getint(),t2=getint(); b=t2-t1; ++i; A[i]=a; B[i]=b;
            if(a==0){ if(b<0)upd(1,1);}
            else if(b==0){
                if(a<0) upd(1,1),upd(d,-1); else upd(1+d,1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,1); else if(An<-r) upd(1,1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,1),upd(-An+d+1,-1);
                    else if(-An>r) upd(1,1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,1); else if(-An<-r) upd(1,1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,1),upd(An+d+1,-1);
                    else if(An>r) upd(1,1);
                }
            }
        }else if(op=='Q'){
            k=getint();
            print(qry(k+d));*o++='\n';
        }else{
            k=getint();
            if(del[k])continue;
            del[k]=1; a=A[k]; b=B[k];
            if(a==0){ if(b<0)upd(1,-1);}
            else if(b==0){
                if(a<0) upd(1,-1),upd(d,1); else upd(1+d,-1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,-1); else if(An<-r) upd(1,-1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,-1),upd(-An+d+1,1);
                    else if(-An>r) upd(1,-1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,-1); 
                    else if(-An<-r) upd(1,-1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,-1),upd(An+d+1,1);
                    else if(An>r) upd(1,-1);
                }
            }
        }
    }return fwrite(buf,1,o-buf,stdout),0;
}

以及这是我贡献的一片红色。

BZOJ 树状数组 bzoj 分类讨论 Comments(2) 2013年6月17日 19:54