![【主席树】【bzoj2161】[hdu4348]](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "【主席树】【bzoj2161】[hdu4348]")
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 400000
using namespace std;
];
],cnt,n,m,x,y,k,rson[],sum[];
bool cmp(node a,node b)
{
return a.x<b.x;
}
void update(int st,int ed,int x,int &y,int v)
{
//printf("%d %d %d %d\n",st,ed,x,y);
;y=++cnt;sum[y]=sum[x]+;
if(st==ed)return;
lson[y]=lson[x];rson[y]=rson[x];
if(v<=mid)
{
update(st,mid,lson[x],lson[y],v);
}else
{
update(mid+,ed,rson[x],rson[y],v);
}
}
int query(int x,int y,int rk)
{
,r=n,a=root[x-],b=root[y];
while(l<r)
{
;
int tmp=sum[lson[b]]-sum[lson[a]];
if(tmp>=rk)r=mid,a=lson[a],b=lson[b];
,a=rson[a],b=rson[b];
}
return l;
}
int main()
{
scanf("%d%d",&n,&m);
;i<=n;i++)scanf("%d",&a[i]),b[i].x=a[i],b[i].h=i;
sort(b+,b+n+,cmp);].x,rank=;
;i<=n;i++)if(b[i].x==now)a[b[i].h]=rank;else
now=b[i].x,rank++,a[b[i].h]=rank;
memset(root,,sizeof(root));
;i<=n;i++)
{
update(,n,root[i-],root[i],a[i]);
}
;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&k);
int last=query(x,y,k);printf("%d\n",last);
}
}
以上是罗oj的模板题，这里输出的答案没有离散回去还有点问题。。先不要交到poj上
下面可以先尝试着用主席树写一下[bzoj2161]。。。虽然ppt的题解上是扔到平衡树里搞？
暑期主席树小专题
要做的事情多着呢。
A：也是一个模（mu）板题，不多说。
B：count on a tree，强制在线，以前就做过了。这里感觉只有query（）需要注意一下的。
#include<cstdio>
#include<algorithm>
#define M 2000005
#define N 200005
using namespace std;
int n,m,cnt,size,tot,last,k,edgenum;
],num[N],pos[N],hash[N],root[N],ls[M],rs[M],sum[M],deep[N],head[N],vet[N],next[N],fa[N][];
];
bool cmp(node a,node b)
{
return a.x<b.x;
}
void add(int u,int v)
{
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
}
void update(int st,int ed,int x,int &y,int nb)
{
//printf("%d %d %d %d\n",st,ed,x,y);
y=++size;sum[y]=sum[x]+;if(st==ed)return;
ls[y]=ls[x];rs[y]=rs[x];
;
if(nb<=mid)update(st,mid,ls[x],ls[y],nb);
,ed,rs[x],rs[y],nb);
}
int lca(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int t=deep[x]-deep[y];
;i<=;i++)<<i)&t)x=fa[x][i];
;i>=;i--)if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
];
}
int query(int x,int y,int rk)
{
];
a=root[pos[a]],b=root[pos[b]],c=root[pos[c]],d=root[pos[d]];
,r=tot;
while(l<r)
{
;
int tmp=sum[ls[a]]+sum[ls[b]]-sum[ls[c]]-sum[ls[d]];
if(tmp>=rk)r=mid,a=ls[a],b=ls[b],c=ls[c],d=ls[d];
,a=rs[a],b=rs[b],c=rs[c],d=rs[d];
}
return hash[l];
}
void dfs(int u)
{
num[++cnt]=u,pos[u]=cnt;
;i<=;i++)
<<i)<=deep[u])fa[u][i]=fa[fa[u][i-]][i-];
else break;
int e=head[u];
)
{
int v=vet[e];
])
{
deep[v]=deep[u]+;
fa[v][]=u;dfs(v);
}
e=next[e];
}
}
int main()
{
scanf("%d%d",&n,&m);
;i<=n;i++)scanf("%d",&a[i]),bx[i].x=a[i],bx[i].h=i;
sort(bx+,bx+n+,cmp);
,now=bx[].x;tot++;hash[tot]=now;
;i<=n;i++)
{
if(bx[i].x==now)a[bx[i].h]=rank;
else
{
rank++;now=bx[i].x;a[bx[i].h]=rank;
tot++;hash[tot]=now;
}
}
int x,y;
;i<=n-;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
cnt=;dfs();
;i<=n;i++)
{
int t=num[i];
update(,tot,root[pos[fa[t][]]],root[i],a[t]);
}
;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&k);
x=x^last;last=query(x,y,k);
printf("%d",last);if(i!=m)printf("\n");
}
}
bzoj2588
C：count on a treeⅡ，八中oj上面基本上都被卡了，又没有很多std供我在hdu上测试。。。就算啦（懒人就是这样，AC无望的题连学都不想学惹
E：也蛮简单的，然而写了一下午。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 400000
using namespace std;
;
],root[N],rson[],sum[];
],back[];
struct node{
int x,h;
}b[];
bool cmp(node a,node b)
{
return a.x<b.x;
}
void update(int st,int ed,int x,int &y,int v)
{
;y=++cnt;sum[y]=sum[x]+;
if(st==ed)return;
lson[y]=lson[x];rson[y]=rson[x];
if(v<=mid)update(st,mid,lson[x],lson[y],v);
,ed,rson[x],rson[y],v);
}
int query(int x,int y,int kth)
{
,r=n,a=root[x-],b=root[y],tmp=;
while(l<=r)
{
if(l==r){
if(back[l]<=kth)tmp+=sum[lson[b]]-sum[lson[a]];
return tmp;
}
;int x=sum[lson[b]]-sum[lson[a]];
,tmp+=x,a=rson[a],b=rson[b];
else r=mid,a=lson[a],b=lson[b];
//printf("====%d %d %d %d %d\n",l,r,mid,x,tmp);
}
return tmp;
}
int main()
{
scanf("%d",&cases);
;cas<=cases;cas++)
{
scanf(;
memset(sum,,sizeof(sum));
memset(root,,sizeof(root));
memset(lson,,sizeof(lson));
memset(rson,,sizeof(rson));
;i<=n;i++)
{
scanf("%d",&a[i]);b[i].x=a[i];b[i].h=i;
}
;i<=n;i++)back[i]=;
sort(b+,b+n+,cmp);
].x,rank=;back[rank]=now;
;i<=n;i++)
if(b[i].x==now)a[b[i].h]=rank;
else now=b[i].x,rank++,back[rank]=b[i].x,a[b[i].h]=rank;
;i<=n;i++)update(,n,root[i-],root[i],a[i]);
printf("Case %d:\n",cas);
;i<=m;i++)
{
int L,R,H;
scanf("%d%d%d",&L,&R,&H);L++;R++;
printf("%d\n",query(L,R,H));
}
}
}
hdu4417 Super Mario
[bzoj2161]布娃娃
QAQ不造为啥这道题做的人这么少。。。是因为太水？还是因为雨荨萌萌的题面？。。。。
我不管，除了读入略坑以外，其它的看起来还是很可做的嘛。
把每一条线段看作插入与删除两个操作，对于它们的耐心值P【i】，（我这里看不到完整的题面，但是从一些std可以看出j喜欢i，当且仅当i被j的线段包围了）
那么思路就来了，把魅力值离散一下，add操作与query操作套一套就可以了。
而且这里也不需要什么继承，一棵root搞定。yep
#include<cstdio>
#include<algorithm>
#define mo 19921228
#define ll long long
#define N 100005
using namespace std;
,n,qn,root=;
],rson[],sum[],back[N];
struct node{
int x,h;
}dat[N];
struct wxx{
int c,k,x,f;
}q[];
bool cmp1(node a,node b)
{
return a.x<b.x;
}
bool cmp2(wxx a,wxx b)
{
if(a.x==b.x)return a.f<b.f;
return a.x<b.x;
}
void work()
{
int add,fir,mdd,prod;
scanf("%d%d%d%d",&add,&fir,&mdd,&prod);
]=x;
;i<=n;i++)
a[i]=(1ll*a[i-]*prod+add+i)%mdd;
}
void add(int &x,int l,int r,int v,int val)
{
)x=++cnt;sum[x]+=val;//printf("%d %d\n",l,r);
if(l==r)return;
;
,r,v,val);
}
int query(int x,int l,int r,int kth)
{
//printf("%d %d\n",l,r);
if(l==r)return l;
//printf("%d %d\n",l,r);
;
,r,kth);
else return query(lson[x],l,mid,kth-sum[rson[x]]);
}
int main()
{
scanf("%d",&n);
work();;i<=n;i++)P[i]=a[i];
work();;i<=n;i++)C[i]=a[i];
work();;i<=n;i++)L[i]=a[i];
work();;i<=n;i++)R[i]=a[i];
//for(int i=1;i<=n;i++)printf("%d ",C[i]);printf("\n");
;i<=n;i++)dat[i].x=C[i],dat[i].h=i;
sort(dat+,dat+n+,cmp1);
].x,rank=;back[]=now;
;i<=n;i++)
if(dat[i].x==now)C[dat[i].h]=rank;else now=dat[i].x,rank++,back[rank]=now,C[dat[i].h]=rank;
//for(int i=1;i<=n;i++)printf("%d ",C[i]); printf("\n");
;i<=n;i++)
{
if(L[i]>R[i])swap(L[i],R[i]);
qn++;q[qn].f=; q[qn].x=L[i]; q[qn].c=C[i];
qn++;q[qn].f=; q[qn].x=P[i]; q[qn].c=; q[qn].k=i;
qn++;q[qn].f=-; q[qn].x=R[i]+; q[qn].c=C[i];
}
sort(q+,q+qn+,cmp2);
//for(int i=1;i<=qn;i++)printf("%d %d %d\n",q[i].x,q[i].f,q[i].c);
ll ans=;
;i<=qn;i++)
{
)add(root,,n,q[i].c,);
)add(root,,n,q[i].c,-);
else if(sum[root]>=q[i].k)
ans=(ans+back[query(root,,n,q[i].k)])%mo;
}
printf("%lld\n",ans);
}
bzoj2161