BZOJ4867 : [Ynoi2017]舌尖上的由乃

时间：2024-03-24 23:36:50

首先通过DFS序将原问题转化为序列上区间加、询问区间kth的问题。

考虑分块，设块大小为$K$，每块维护排序过后的$pair(值,编号)$。

对于修改，整块的部分可以直接打标记，而零碎的两块因为本来有序，故可以按照修改区间将其分离成两个有序序列$A$(不在修改区间)和$B$(在修改区间)。

对$B$每个值都加上一个常数，再与$A$归并排序，即可在$O(K)$的时间内修改零碎的两块。

对于查询，首先将零碎的两块用同样的方法分离出来，然后二分答案，在每个整块二分查找个数即可，时间复杂度$O(\frac{n}{K}\log^2n)$。

当$K$取$\sqrt{n}\log n$时取得最优复杂度$O(n\sqrt{n}\log n)$。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef pair<int,int>P;

const int N=100010,K=12,M=(N>>K)+5,BUF=6000000;

char Buf[BUF],*buf=Buf;

int n,m,i,lim,op,x,y,g[N],w[N],nxt[N],stq[N],enq[N],dfn;

int block,st[M],en[M],tag[M];P a[N<<1];

inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}

inline void add(int x,int y,int z){w[y]=z;nxt[y]=g[x];g[x]=y;}

void dfs(int x,int y){

  stq[x]=++dfn;

  a[dfn]=P(y,dfn);

  for(int i=g[x];i;i=nxt[i])dfs(i,y+w[i]);

  enq[x]=dfn;

}

inline void change(int o,int l,int r,int p){

  static P A[N],B[N];

  int ca=0,cb=0,i,j,k=st[o];

  for(i=st[o];i<=en[o];i++)if(a[i].second<l||a[i].second>r)A[++ca]=a[i];else B[++cb]=a[i],B[cb].first+=p;

  i=j=1;

  while(i<=ca&&j<=cb)a[k++]=A[i]<B[j]?A[i++]:B[j++];

  while(i<=ca)a[k++]=A[i++];

  while(j<=cb)a[k++]=B[j++];

}

inline void modify(int x,int y,int p){

  int X=x>>K,Y=y>>K,i;

  for(i=X+1;i<Y;i++)tag[i]+=p;

  change(X,x,y,p);

  if(X<Y)change(Y,x,y,p);

}

inline int ask(int o,int p){

  int l=st[o],r=en[o],mid,t=l-1;

  if(l>r)return 0;

  p-=tag[o];

  while(l<=r)if(a[mid=(l+r)>>1].first<=p)l=(t=mid)+1;else r=mid-1;

  return t-st[o]+1;

}

inline int kth(int x,int y,int k){

  if(k>y-x+1)return -1;

  int X=x>>K,Y=y>>K,i,s=n+1,e=n;

  tag[block+1]=tag[X];

  for(i=st[X];i<=en[X];i++)if(a[i].second>=x&&a[i].second<=y)a[++e]=a[i];

  st[block+1]=s,en[block+1]=e;

  s=e+1;

  if(X<Y){

    tag[block+2]=tag[Y];

    for(i=st[Y];i<=en[Y];i++)if(a[i].second<=y)a[++e]=a[i];

  }

  st[block+2]=s,en[block+2]=e;

  int l=0,r=lim,mid,t,ans;

  while(l<=r){

    mid=(l+r)>>1;

    t=ask(block+1,mid)+ask(block+2,mid);

    for(i=X+1;i<Y&&t<k;i++)t+=ask(i,mid);

    if(t>=k)r=(ans=mid)-1;else l=mid+1;

  }

  return ans;

}

int main(){

  fread(Buf,1,BUF,stdin);read(n),read(m),read(x);

  for(i=2;i<=n;i++)read(x),read(y),add(x,i,y),lim+=y;

  dfs(1,0);

  block=n>>K;

  for(i=1;i<=n;i++)en[i>>K]=i;

  for(i=n;i;i--)st[i>>K]=i;

  for(i=0;i<=block;i++)sort(a+st[i],a+en[i]+1);

  while(m--){

    read(op),read(x),read(y);

    if(op==1)printf("%d\n",kth(stq[x],enq[x],y));else modify(stq[x],enq[x],y),lim+=y;

  }

  return 0;

}

　　

相关文章