欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

4448: [Scoi2015]情报传递|主席树|离线操作

程序员文章站 2023-12-25 12:25:09
可以把所有的操作离线,然后树链剖分将所有人搜集情报的时间加入到主席树中,查询的时候可以直接查询搜集情报时间≤i?C[i]?1的人的个数 时间复杂度n?log22n,空间复杂...

可以把所有的操作离线,然后树链剖分将所有人搜集情报的时间加入到主席树中,查询的时候可以直接查询搜集情报时间≤i?C[i]?1的人的个数
时间复杂度n?log22n,空间复杂度n?log2n

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define N 202020
using namespace std;
int sc()
{
    int i=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i*f;
}
int opt[N],X[N],Y[N],C[N];
int sum[N*20],ch[N*20][2],tim[N],root[N];
int fa[N],top[N],size[N],deep[N],S[N],wh[N];
int head[N],nxt[N],lst[N];
int n,m,tot,cnt,num;
void insert(int x,int y)
{
    lst[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
void dfs(int x)
{
    size[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        deep[lst[i]]=deep[x]+1;
        fa[lst[i]]=x;
        dfs(lst[i]);
        size[x]+=size[lst[i]];
    }
}
void _dfs(int x,int htp)
{
    int k=0;S[x]=++cnt;top[x]=htp;wh[cnt]=x;
    for(int i=head[x];i;i=nxt[i])
        if(size[lst[i]]>size[k])k=lst[i];
    if(!k)return ;_dfs(k,htp);
    for(int i=head[x];i;i=nxt[i])
        if(lst[i]!=k)_dfs(lst[i],lst[i]);
}
void add(int pre,int &x,int l,int r,int v)
{
    if(!x)x=++num;
    sum[x]=sum[pre]+1;
    if(l==r)return;
    int mid=l+r>>1;
    if(v<=mid)
        ch[x][1]=ch[pre][1],
        add(ch[pre][0],ch[x][0],l,mid,v);
    else
        ch[x][0]=ch[pre][0],
        add(ch[pre][1],ch[x][1],mid+1,r,v);
}
int query(int x,int y,int c)
{
    int L=root[x-1],R=root[y],l=1,r=m,res=0;
    while(l!=r)
    {
        int mid=l+r>>1;
        if(c<=mid)
            L=ch[L][0],R=ch[R][0],r=mid;
        else
            res+=sum[ch[R][0]]-sum[ch[L][0]],
            L=ch[L][1],R=ch[R][1],l=mid+1;
    }
    res+=(c>=l?sum[R]-sum[L]:0);
    return res;
}   
void solve(int x,int y,int c)
{
    int sum=0,res=deep[x]+deep[y];
    while(top[x]!=top[y])
    {
        if(deep[top[x]]

上一篇:

下一篇: