over 3 years ago

之前写了却没过的题 这次改了改过了……但是不知道为啥跑的超级慢
有时间搞搞优化吧
sol:
1、离线,删点变加点
2、每加一个点就在前面的区间统计比他大的,后面的区间统计比他小的计入result。加的话就是一路修改每棵平衡树都加点就好了
findpoint是重点,获得的是>=number的最小的数的位置

int findpoint(int pos,int number)
{
    int minn=inf,k=0;
    while (pos!=0)
    {
        if (num[pos]==number) return pos;
        if (num[pos]>number) 
        {
            if (num[pos]<minn) {minn=num[pos];k=pos;}
            pos=son[pos][0];
        }
        else pos=son[pos][1];       
    }
    return k;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 100001
#define inf 1000000000
#define maxm 2000001
using namespace std;
int a[maxn]={0},tree[maxn]={0},dy[maxn]={0};
int fa[maxm]={0},son[maxm][2]={0},size[maxm]={0},num[maxm]={0};
int n,m,i,j,k,tot=0;long long result=0;
int bit[maxn]={0};
int querys[50001]={0};
long long ans[50001]={0};
bool can[maxn];
int readln()
{
    char c=getchar();int result=0,bj=1;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') c=getchar(),bj=-1;
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
int judge(int x){return son[fa[x]][1]==x;}
void update(int now)
{
    if (now!=0) size[now]=1+size[son[now][0]]+size[son[now][1]];
}
void setson(int father,int x,int r)
{
    son[father][r]=x;fa[x]=father;update(father);
}
void rot(int now)
{
    int r=(judge(now)^1),father=fa[now],grand=fa[father];
    setson(father,son[now][r],r^1);
    setson(now,father,r);
    if (grand!=0)setson(grand,now,son[grand][0]==father?0:1);
      else fa[now]=0;
}
void splay(int x,int now,int aim)
{
    for (;fa[now]!=aim;rot(now))
      if (fa[fa[now]]==aim);
      else if (judge(now)==judge(fa[now])) rot(fa[now]);else rot(now);
    if (aim==0) tree[x]=now;
}
void insert(int x,int pos,int number)
{
    if (num[pos]<number)
    {                                                 
        if (son[pos][1]==0)
        {
            son[pos][1]=++tot;fa[tot]=pos;num[tot]=number;size[tot]=1;
            splay(x,tot,0);
        }
        else insert(x,son[pos][1],number);
    }
    else
    {
        if (!son[pos][0])
        {
            son[pos][0]=++tot;fa[tot]=pos;num[tot]=number;size[tot]=1;
            splay(x,tot,0);
        }
        else insert(x,son[pos][0],number);
    }   
}
int findpoint(int pos,int number)
{
    int minn=inf,k=0;
    while (pos!=0)
    {
        if (num[pos]==number) return pos;
        if (num[pos]>number) 
        {
            if (num[pos]<minn) {minn=num[pos];k=pos;}
            pos=son[pos][0];
        }
        else pos=son[pos][1];       
    }
    return k;
}
int query(int x,int pos,int number,int d)
{  
    k=findpoint(pos,number);
    if (k==0) 
    {if (d==1) return 0;else return size[pos];}
    splay(x,k,0);
    if (num[k]==number){if (d==1) return size[son[k][1]];else return size[son[k][0]];       }
    else{if (d==1) return size[son[k][1]]+1;else return size[son[k][0]];        }
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int number)
{
    for (i=pos;i<=n;i=i+lowbit(i)) 
    {
     if (tree[i]==0) {tree[i]=++tot;num[tot]=number;size[tot]=1;}
      else insert(i,tree[i],number);        
    }
}
int  querybit(int pos,int number,int delta)
{int result=0;
    for (i=pos;i>0;i=i-lowbit(i))
        result+=query(i,tree[i],number,delta);
    return result;
}
void addbit(int x)
{
    for (i=x;i<=n;i+=lowbit(i)) bit[i]++;
}
int querybittree(int  x)
{
    int result=0;
    for (i=x;i>0;i-=lowbit(i)) result+=bit[i];
    return result;
}
int main()
{
    int i,j,k;
    n=readln();m=readln();
    memset(can,true,sizeof(can));
    for (i=1;i<=n;i++) a[i]=readln(),dy[a[i]]=i;
    for (i=1;i<=m;i++) querys[i]=readln(),can[querys[i]]=false;
    for (i=1;i<=n;i++)
     if (can[a[i]])
    {
        result+=querybittree(n)-querybittree(a[i]);
        addbit(a[i]);
        add(dy[a[i]],a[i]);
    }
   for (i=m;i>=1;i--)
    { 
        k=querys[i];
        result+=querybit(dy[k],k,1)+querybit(n,k,0)-querybit(dy[k],k,0);
        add(dy[k],k);
        ans[i]=result;
    }
    for (i=1;i<=m;i++) printf("%lld\n",ans[i]);
}
← 【bzoj3720】【块状树】gty的妹子树 【bzoj1854】【匈牙利】游戏 →
 
comments powered by Disqus