[JZOJ6089]【CodeChef 2014 April Challenge】Final Battle of C

Description

Solution

又是一道大数据结构

由于有一个下取整，这就导致了不同时间的修改值是不能简单的直接加在一起的。

容易发现，1操作的影响只会影响到距离不超过log的点。

这样我们很容易得到一个(qlog nlog ^2V)的做法

同一深度的修改有一种套路是维护BFS序。
对于子树内的点，我们将log个深度对应的BFS序区间减去相应的影响。

对于修改点的log个有用的祖先，我们也类似操作，注意重复影响的要减去。

这样我们每次修改要修改(log^2V)段区间，用线段树维护又有一个log
由于每个点只会变负一次，我们只需要维护区间减得同时维护区间最小值，发现区间区间最小值变非正了就暴力走下去改，更新答案，这样每个点只会改一次，复杂度是有保证的。

虽然这样已经能通过这道题了（我怎么会说这跑的比log^2还快）
我们还要寻找更优秀的算法。

我们不妨先不修改子树，每次修改点只改祖先。记录(tag_{i,j})表示点i对距离自己为(j)的儿子的影响

那么每次修改就变成了(log^2)的了，我们只需要对它的log的祖先，每一个改一下标记。
现在可以支持单点查询是否变非正，直接跳log级祖先查一下就好。

但我们要求某个时间的子树内非正点的个数，如果我们能快速算出每个点变非正的时间就好了。

可以整体二分/CDQ分治！

我们对于所有的操作按时间分治，对于分治区间([l,r])记一个点集S，表示S中的点在时间[l,r]变非正，我们将出现时间在mid之前的所有操作都处理，一个个查询S中的点是否变非正，看是下放左区间还是右区间。

分析复杂度，每个点会查询log次，每次查询跳log个祖先，两个log
每个操作会用log次，每次时间log^2，这不可取！

我们发现如果每次都把操作暴力插回撤销，这非常的浪费。
因为我们总的需要查询的(tag_{i,j})的改变次数只有$nlog^2 $

我们可以将(tag)数组可持久化，用一个链表或者vector存下每次改变的时间，查询的时候只需要移一下指针即可，容易看出指针的移动总次数只有(nlog ^2)

那么总的时间复杂度就降到了(O(Qlog^2))

Code

//why always data structures ????
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,b) for(int i=a;i>=b;--i)
#define N 100005
#define LL long long
using namespace std;
int fs[N],nt[2*N],dt[2*N],pr[N],n,m,w[N],dfw[N],sz[N],dfn[N],ans[N],m1,ask[N][3],f[N],dep[N];
LL sm[N];


//tree_array
int c[N];
int lowbit(int k)
{
    return k&-k;
}
int get(int k)
{
    int s=0;
    while(k) s+=c[k],k-=lowbit(k);
    return s; 
}
void put(int k)
{
    while(k<=n) c[k]++,k+=lowbit(k);
}

//prepare
void link(int x,int y)
{   
    nt[++m1]=fs[x];
    dt[fs[x]=m1]=y;
}
void dfs(int k,int fa)
{
    f[k]=fa;
    dfw[dfn[k]=++dfn[0]]=k;
    dep[k]=dep[fa]+1;
    sz[k]=1;
    for(int i=fs[k];i;i=nt[i]) 
    {
        int p=dt[i];
        if(p!=fa) dfs(p,k),sz[k]+=sz[p];
    }
}

//solve

struct node
{
    LL v,t;     
}; 
vector<node> tag[N][32];
int le[N][32],now[N][32],d[N],u1[N],u2[N],ts[N];

void ins(int k,int s,int ti)
{
    if(!s||!k) return;
    int v=s;
    for(int c=0;v;c++) 
    {
        int vl=(f[k])?v-(v>>2):v;
        if(le[k][c]==0) tag[k][c].push_back((node){vl,ti});
        else tag[k][c].push_back((node){vl+tag[k][c][le[k][c]-1].v,ti});
        le[k][c]++;
        v>>=1;
    }
    ins(f[k],s>>1,ti);
}

LL query(int k,int ti)
{
    LL s=0;
    for(int p=0;p<=31&&k;k=f[k],p++)
    {
        while(now[k][p]<le[k][p]-1&&tag[k][p][now[k][p]+1].t<=ti) now[k][p]++;
        while(now[k][p]>0&&tag[k][p][now[k][p]].t>ti) now[k][p]--;
        if(now[k][p]<le[k][p]&&tag[k][p][now[k][p]].t<=ti) s+=tag[k][p][now[k][p]].v;
    } 
    return s;
}
void doit(int l,int r,int x,int y)
{
    if(x>y) return;
    if(l==r) {fo(i,x,y) ts[d[i]]=l;return;}
    int mid=(l+r)>>1;
    u1[0]=0,u2[0]=0;
    fo(i,y)
    {
        if(pr[d[i]]<=query(d[i],mid)) u1[++u1[0]]=d[i];
        else u2[++u2[0]]=d[i];
    }
    fo(j,1,u1[0]) d[x+j-1]=u1[j];
    fo(j,u2[0]) d[x+u1[0]+j-1]=u2[j];
    int md=x+u1[0]-1;
    doit(l,mid,md);
    doit(mid+1,r,md+1,y);
}

bool cmp(int x,int y)
{
    return ts[x]<ts[y];
}
int main()
{
    cin>>n;
    fo(i,n) scanf("%d",&pr[i]);
    
    fo(i,n-1)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        link(x,y),link(y,x);
    }
    dfs(1,0);

    int q;
    cin>>q;
    fo(i,q) 
    {
        scanf("%d%d",&ask[i][0],&ask[i][1]);
        if(ask[i][0]==1) 
        {
            scanf("%d",&ask[i][2]);
            ins(ask[i][1],ask[i][2],i);
        }
    }
    fo(i,n) d[i]=i;
    doit(1,q+1,n);

    sort(d+1,d+n+1,cmp);
    for(int i=1,j=1;i<=q;i++)
    {
        while(j<=n&&ts[d[j]]<=i) put(dfn[d[j]]),j++;
        if(ask[i][0]==2) printf("%dn",get(dfn[ask[i][1]]+sz[ask[i][1]]-1)-get(dfn[ask[i][1]]-1));
    }
}

（编辑：52站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!