小清新线段树

小清新线段树的概念是由jiry_2提出的,区别于zkw(重口味)线段树命名。这里我的理解是可以归为一类结合时间复杂度分析以及懒标记应用的非传统线段树。不过既为非传统,这类题目总体来说还是做法各异,下面就结合题目做一些分析。


入门难度

1.bzoj 3211 花神游历各国

区间求和,区间开根号(下取整)

因为只有开根号操作,所以最后不是1就是0,且一个数开根号次数级别的,1e9的数最多开5次。所以就怎么暴力都行了,比如判断当前区间最大值是否是1,或者直接记录访问每个节点的次数是否达到5次,用于剪枝。时间复杂度。

2.bzoj 3333 排队计划

这个题其实不是很入门

有一个排列,每次修改是给一个位置x,先拿出x及之后所有小于等于a[x]的数,从小到大排序后,再放回空位中,一开始及每次操作完都要输出当前排列的逆序对数。

计算逆序对数就用传统方法,把以每个位置为开头的逆序对数加起来。那么通过观察发现,这个排序操作会抹掉x及之后所有小于等于a[x]的那些位置的贡献,并且不会对其他不动的位置的贡献造成影响。这样每次用线段树通过判断最小值,每次暴力下去找到需要清除贡献的地方即可,因为每个点只会被清除一次,那么平摊下来总时间复杂度就是。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
#define N 500010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
int a[N],n,m;
int h[N],cnt;
int val[N],c[N];
struct node
{
    int l,r,mn;
    ll val;
} t[N<<2];
int ask(int x)
{
    int ans=0;
    for(;x;x-=x&(-x)) ans+=c[x];
    return ans;
}
void change(int x,int y)
{
    for(;x<=cnt;x+=x&(-x)) c[x]+=y;
}
void push_up(int p)
{
    t[p].mn=min(t[ls(p)].mn,t[rs(p)].mn);
    t[p].val=t[ls(p)].val+t[rs(p)].val;
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r)
    {
        t[p].val=val[l];
        t[p].mn=a[l];
        return;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void change(int p,int l,int r,int y)
{
    if(t[p].r<l||r<t[p].l||t[p].mn>y) return;
    if(t[p].l==t[p].r)
    {
        t[p].val=0;
        t[p].mn=INF;
        a[t[p].l]=INF;
        return;
    }
    change(ls(p),l,r,y);
    change(rs(p),l,r,y);
    push_up(p);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",a+i);
        h[i]=a[i];
    }
    cnt=n;
    sort(h+1,h+cnt+1);
    cnt=unique(h+1,h+cnt+1)-h-1;
    for(int i=n;i>=1;--i)
    {
        a[i]=lower_bound(h+1,h+cnt+1,a[i])-h;
        val[i]=ask(a[i]-1);
        change(a[i],1);
    }
    build(1,1,n);
    printf("%lld\n",t[1].val);
    while(m--)
    {
        int x;
        scanf("%d",&x);
        if(a[x]!=INF) change(1,x,n,a[x]);
        printf("%lld\n",t[1].val);
    }
    return 0;
}

 


进阶难度

1.Petrozavodsk Winter-2018. AtCoder Contest I. ADD, DIV, MAX

维护序列,支持区间加,区间整除,区间求最大值。

我们定义线段树上每个节点势能函数为,或者直观理解就是这个区间除以多少次2就会完全相同。那么由于线段树一共个节点,初始总势能为。因为线段树区间操作会访问个节点,所以一次区间加操作至多增加。由于我们修改时访问一个节点就会使该节点势能减一,所以总的时间复杂度是。

具体实现就是线段树维护最大值最小值,以及加法的懒标记,对于除法操作如果当前区间的最大值和最小值的改变量是相同的,那么对于这个区间来说,除法操作就可以看成整体加上一个数,否则暴力递归到左右子树。

#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct node
{
    int l,r,min,max,add;
} t[N<<4];
int n,m;
void push_up(int p)
{
    t[p].min=min(t[ls(p)].min,t[rs(p)].min);
    t[p].max=max(t[ls(p)].max,t[rs(p)].max);
}
void update(int p,int y)
{
    t[p].add+=y;
    t[p].min+=y;
    t[p].max+=y;
}
void push_down(int p)
{
    if(t[p].add)
    {
        update(ls(p),t[p].add);
        update(rs(p),t[p].add);
        t[p].add=0;
    }
}

void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        t[p].min=t[p].max=x;
        t[p].add=0;
        return ;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void Add(int p,int l,int r,int x)
{
    if(t[p].r<l || r<t[p].l) return;
    if(l<=t[p].l && t[p].r<=r)
    {
        update(p,x);
        return;
    }
    push_down(p);
    Add(ls(p),l,r,x);
    Add(rs(p),l,r,x);
    push_up(p);
}
void Div(int p,int l,int r,int x)
{
    if(t[p].r<l||r<t[p].l|| (t[p].max==0)) return;
    if(l<=t[p].l&&t[p].r<=r &&  t[p].min/x-t[p].min==t[p].max/x-t[p].max)
    {
        update(p,t[p].min/x-t[p].min);
        return;
    }
    push_down(p);
    Div(ls(p),l,r,x);
    Div(rs(p),l,r,x);
    push_up(p);
}
int Ask(int p,int l,int r)
{
    if(r<t[p].l || t[p].r<l) return 0;
    if(l<=t[p].l && t[p].r<=r) return t[p].max;
    push_down(p);
    return max(Ask(ls(p),l,r),Ask(rs(p),l,r));
}
int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int op,l,r,x;
        scanf("%d%d%d%d",&op,&l,&r,&x);
        ++l;++r;
        if(op==0) Add(1,l,r,x);
        else if(op==1)
        {
            if(x>1) Div(1,l,r,x);
        }
        else printf("%d\n",Ask(1,l,r));
    }
    return 0;
}

2.Codeforces 438D The Child and Sequence

维护序列,支持区间求和,区间模一个数,单点修改。

首先需要用一个很好证明的式子,也就是说模操作会让每个数至少除以2。由于只有单点修改,那么就比上一个题好分析了,势能函数是每个区间最大值除以2的次数,初始总势能,单点修改还是,改变了个点,每个点充能,所以总的时间复杂度。

那么具体实现额外维护最大值,当区间最大值小于模数就剪枝,否则暴力下去。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct node
{
    int l,r,mx;
    ll sum;
} t[N<<2];
int n,m;
void push_up(int p)
{
    t[p].mx=max(t[ls(p)].mx,t[rs(p)].mx);
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        t[p].mx=x;
        t[p].sum=x;
        return ;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void change(int p,int l,int r,int y)
{
    if(t[p].r<l||r<t[p].l||t[p].mx<y) return;
    if(t[p].l==t[p].r)
    {
        t[p].sum=t[p].mx=t[p].mx%y;
        return;
    }
    change(ls(p),l,r,y);
    change(rs(p),l,r,y);
    push_up(p);
}
void change(int p,int x,int y)
{
    if(t[p].l==t[p].r)
    {
        t[p].sum=t[p].mx=y;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(ls(p),x,y);
    else change(rs(p),x,y);
    push_up(p);
}
ll ask(int p,int l,int r)
{
    if(t[p].r<l||r<t[p].l) return 0;
    if(l<=t[p].l && t[p].r<=r) return t[p].sum;
    return ask(ls(p),l,r)+ask(rs(p),l,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",ask(1,l,r));
        }
        else if(opt==2)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            change(1,l,r,x);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            change(1,x,y);
        }
    }
    return 0;
}

3.hdu 5306 Gorgeous Sequence

维护序列,区间对一个数取min,询问区间最小值,区间求和

这个题的做法就比较科幻了。

《Segment tree Beats!》课件中关于时间复杂度的证明一些是错误的

可以参考这里,http://jiry-2.blog.uoj.ac/blog/1404

时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct node
{
    int fi,se,cnt,cov;
    ll sum;
} t[N<<2];
int n,m;
void read(int &x)
{
    static char ch;
    while(!isdigit(ch=getchar()));
    x=ch-'0';
    while(isdigit(ch=getchar()))
        x=x*10+(ch-'0');
}
void push_up(int p)
{
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
    if(t[ls(p)].fi==t[rs(p)].fi)
    {
        t[p].fi=t[ls(p)].fi;
        t[p].se=max(t[ls(p)].se,t[rs(p)].se);
        t[p].cnt=t[ls(p)].cnt+t[rs(p)].cnt;
    }
    else if(t[ls(p)].fi>t[rs(p)].fi)
    {
        t[p].fi=t[ls(p)].fi;
        t[p].se=max(t[ls(p)].se,t[rs(p)].fi);
        t[p].cnt=t[ls(p)].cnt;
    }
    else
    {
        t[p].fi=t[rs(p)].fi;
        t[p].se=max(t[ls(p)].fi,t[rs(p)].se);
        t[p].cnt=t[rs(p)].cnt;
    }
}
void build(int p,int l,int r)
{
    t[p].cov=-1;
    if(l==r)
    {
        read(t[p].fi);
        t[p].se=-1;
        t[p].cnt=1;
        t[p].sum=t[p].fi;
        return;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void update(int p,int y)
{
    if(y>=t[p].fi) return;
    t[p].sum-=1LL*t[p].cnt*(t[p].fi-y);
    t[p].fi=t[p].cov=y;
}
void push_down(int p)
{
    if(t[p].cov!=-1)
    {
        update(ls(p),t[p].cov);
        update(rs(p),t[p].cov);
        t[p].cov=-1;
    }
}
void change(int p,int l,int r,int L,int R,int y)
{
    if(r<L||R<l||t[p].fi<=y) return;
    if(L<=l && r<=R)
    {
        if(l==r)
        {
            t[p].sum=t[p].fi=y;
            t[p].se=-1;
            t[p].cnt=1;
            return;
        }
        if(t[p].se<y && y<t[p].fi)
        {
            update(p,y);
            return;
        }
    }
    push_down(p);
    int mid=l+r>>1;
    change(ls(p),l,mid,L,R,y);
    change(rs(p),mid+1,r,L,R,y);
    push_up(p);
}
int ask_max(int p,int l,int r,int L,int R)
{
    if(r<L||R<l) return -1;
    if(L<=l && r<=R) return t[p].fi;
    push_down(p);
    int mid=l+r>>1;
    return max(ask_max(ls(p),l,mid,L,R),ask_max(rs(p),mid+1,r,L,R));
}
ll ask_sum(int p,int l,int r,int L,int R)
{
    if(r<L||R<l) return 0;
    if(L<=l && r<=R) return t[p].sum;
    push_down(p);
    int mid=l+r>>1;
    return ask_sum(ls(p),l,mid,L,R)+ask_sum(rs(p),mid+1,r,L,R);
}
int main()
{
    int T;
    read(T);
    while(T--)
    {
        read(n);read(m);
        build(1,1,n);
        while(m--)
        {
            int opt,x,y,t;
            read(opt);read(x);read(y);
            if(opt==0)
            {
                read(t);
                change(1,1,n,x,y,t);
            }
            else if(opt==1)
                printf("%d\n",ask_max(1,1,n,x,y));
            else
                printf("%lld\n",ask_sum(1,1,n,x,y));
        }
    }
    return 0;
}

 

4.hdu 5634 Rikka with Phi

维护序列,区间赋值,区间取phi,区间求和。

首先根据定义以及相关公式,知道一个大于2的正整数的欧拉函数都是偶数,一个偶数的欧拉函数就至少小了一半,那么一个数能做的次数也就是级别的。

根据前面几个题,这个题的操作就很好想了,如果当前区间的数都相同,那么区间取phi的操作就转化成了区间赋值,同样的打标记即可,不同的话就暴力下去。

时间复杂度是一个log的就比较确信了,然而并不会证。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
#define MAXN 10000000
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
int prime[MAXN+5],phi[MAXN+5],tot;
bool vis[MAXN+5];
struct node
{
    int l,r,max,min,cov;
    ll sum;
} t[N<<2];
int n,m;
void getprime()
{
    phi[1]=1;
    for(int i=2;i<=MAXN;++i)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot && prime[j]<=MAXN/i;++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}
void push_up(int p)
{
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
    t[p].max=max(t[ls(p)].max,t[rs(p)].max);
    t[p].min=min(t[ls(p)].min,t[rs(p)].min);
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    t[p].cov=-1;
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        t[p].sum=t[p].max=t[p].min=x;
        return ;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void update(int p,int y)
{
    t[p].sum=1LL*y*(t[p].r-t[p].l+1);
    t[p].max=t[p].min=y;
    t[p].cov=y;
}
void push_down(int p)
{
    if(t[p].cov!=-1)
    {
        update(ls(p),t[p].cov);
        update(rs(p),t[p].cov);
        t[p].cov=-1;
    }
}
void change(int p,int l,int r)
{
    if(t[p].r<l||r<t[p].l) return;
    if(l<=t[p].l && t[p].r<=r && t[p].max==t[p].min)
    {
        update(p,phi[t[p].max]);
        return;
    }
    push_down(p);
    change(ls(p),l,r);
    change(rs(p),l,r);
    push_up(p);
}
void cover(int p,int l,int r,int y)
{
    if(t[p].r<l||r<t[p].l) return;
    if(l<=t[p].l && t[p].r<=r)
    {
        update(p,y);
        return;
    }
    push_down(p);
    cover(ls(p),l,r,y);
    cover(rs(p),l,r,y);
    push_up(p);
}
ll ask(int p,int l,int r)
{
    if(t[p].r<l||r<t[p].l) return 0;
    if(l<=t[p].l && t[p].r<=r) return t[p].sum;
    push_down(p);
    return ask(ls(p),l,r)+ask(rs(p),l,r);
}
int main()
{
    getprime();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--)
        {
            int opt,l,r,x;
            scanf("%d%d%d",&opt,&l,&r);
            if(opt==1) change(1,l,r);
            else if(opt==2)
            {
                scanf("%d",&x);
                cover(1,l,r,x);
            }
            else printf("%lld\n",ask(1,l,r));
        }
    }
    return 0;
}

 

一类区间分治技巧

对于一类区间询问问题,如果可以离线并且可以快速合并区间信息那么就有一个非常实用的分治方法。首先我们对总区间分治下去,当前区间[l , r]中点为mid,那么我们将所有的询问分成三类,一类包括mid这个点,一类完全在左侧,一类完全在右侧,我们只要在当前这层解决第一类的所有询问,后两类分治下去即可。怎么快速的求呢?方法也非常简单,因为信息可以快速合并,那么我们以mid为界,往前处理出所有后缀信息,往后处理出所有前缀信息,对于一个跨过mid的询问,拿两部分拼一下就算出答案了!

比在线算法优秀的地方在于可以优雅的去掉询问数所乘的log。

练习题目

1.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest J. Subsequence Sum Queries

考虑背包dp,如果用普通的线段树,时间复杂度,因为拆成logn个区间,要完全合并两个背包log次,合并一次(循环卷积)复杂度是,必T无疑。用优秀的分治就可以降到。

#include<bits/stdc++.h>
using namespace std;
#define N 200010
const int mod=1e9+7;
struct node
{
    int l,r,o;
} t[N],tmp[N];
int n,m,len;
int sub[N][22],pre[N][22];
int a[N],ans[N];
int calc(int *f,int *g)
{
    int ans=0;
    for(int i=0;i<m;++i)
    {
        ans+=1LL*f[i]*g[(m-i)%m]%mod;
        if(ans>=mod) ans-=mod;
    }
    return ans;
}
void solve(int l,int r,int L,int R)
{
    if(l>r||L>R) return ;
    int mid=l+r>>1;
    int x=L-1,y=R+1,now=L,j;
    for(int i=L;i<=R;++i)
        if(t[i].r<mid) tmp[++x]=t[i];
        else if(t[i].l>mid) tmp[--y]=t[i];
        else t[now++]=t[i];

    sub[mid+1][0]=1;
    for(int i=1;i<m;++i) sub[mid+1][i]=0;
    for(int i=mid;i>=l;--i)
        for(int j=0;j<m;++j)
            sub[i][j]=(sub[i+1][j]+sub[i+1][(j-a[i]+m)%m])%mod;

    pre[mid][0]=1;
    for(int i=1;i<m;++i) pre[mid][i]=0;
    for(int i=mid+1;i<=r;++i)
        for(int j=0;j<m;++j)
            pre[i][j]=(pre[i-1][j]+pre[i-1][(j-a[i]+m)%m])%mod;

    for(int i=L;i<now;++i)
        ans[t[i].o]=calc(sub[t[i].l],pre[t[i].r]);

    for(int i=L;i<=x;++i) t[i]=tmp[i];
    for(int i=y;i<=R;++i) t[i]=tmp[i];
    solve(l,mid-1,L,x);
    solve(mid+1,r,y,R);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        a[i]%=m;
    }
    scanf("%d",&len);
    for(int i=1;i<=len;++i)
    {
        scanf("%d%d",&t[i].l,&t[i].r);
        t[i].o=i;
    }
    solve(1,n,1,len);
    for(int i=1;i<=len;++i)
        printf("%d\n",ans[i]);
    return 0;
}

2.2018 Multi-University Training Contest 3 Problem J. Rectangle Radar Scanner 

对x轴分治,对于y用线段树维护一下就好了

时间复杂度

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
#define M 1000010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
const int INF=0x3f3f3f3f;
struct segment
{
    int l,r;
    int min,max,prod;
} t[N<<2];
struct REC
{
    int xl,xr,yl,yr,o;
} rec[M],tmp[M];
int n,m,K;
int mn[M],mx[M],prod[M];
pair<int,int> val[N];
bool cmpl(const REC &a,const REC &b)
{
    return a.xl>b.xl;
}
bool cmpr(const REC &a,const REC &b)
{
    return a.xr<b.xr;
}
void push_up(int p)
{
    t[p].min=min(t[ls(p)].min,t[rs(p)].min);
    t[p].max=max(t[ls(p)].max,t[rs(p)].max);
    t[p].prod=1LL*t[ls(p)].prod*t[rs(p)].prod%K;
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    t[p].min=INF;
    t[p].max=-INF;
    t[p].prod=1;
    if(l==r) return;
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
}
void insert(int p,int x,int y)
{
    if(t[p].l==t[p].r)
    {
        t[p].min=min(t[p].min,y);
        t[p].max=max(t[p].max,y);
        t[p].prod=1LL*t[p].prod*y%K;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) insert(ls(p),x,y);
    else insert(rs(p),x,y);
    push_up(p);
}
void ask(int p,int x)
{
    if(rec[x].yl<=t[p].l && t[p].r<=rec[x].yr)
    {
        int o=rec[x].o;
        mn[o]=min(mn[o],t[p].min);
        mx[o]=max(mx[o],t[p].max);
        prod[o]=1LL*prod[o]*t[p].prod%K;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(rec[x].yl<=mid) ask(ls(p),x);
    if(rec[x].yr>mid) ask(rs(p),x);
}
void travel(int p)
{
    if(t[p].min==INF) return;
    t[p].min=INF;
    t[p].max=-INF;
    t[p].prod=1;
    if(t[p].l==t[p].r) return;
    travel(ls(p));
    travel(rs(p));
}
void solve(int l,int r,int L,int R)
{
    if(l>r||L>R) return;
    int mid=l+r>>1;
    int x=L-1,y=R+1,now=L,j;
    for(int i=L;i<=R;++i)
        if(rec[i].xr<mid) tmp[++x]=rec[i];
        else if(rec[i].xl>mid) tmp[--y]=rec[i];
        else rec[now++]=rec[i];
    sort(rec+L,rec+now,cmpl);
    j=mid+1;
    for(int i=L;i<now;++i)
    {
        while(j>rec[i].xl)
        {
            --j;
            insert(1,val[j].first,val[j].second);
        }
        ask(1,i);
    }
    travel(1);
    sort(rec+L,rec+now,cmpr);
    j=mid;
    for(int i=L;i<now;++i)
    {
        while(j<rec[i].xr)
        {
            ++j;
            insert(1,val[j].first,val[j].second);
        }
        ask(1,i);
    }
    travel(1);
    for(int i=L;i<=x;++i) rec[i]=tmp[i];
    for(int i=y;i<=R;++i) rec[i]=tmp[i];
    solve(l,mid-1,L,x);
    solve(mid+1,r,y,R);
}
void read()
{
    int a[2],b[2],c[2],d[2];
    int p,q,r,mod;
    scanf("%d%d%d%d%d%d%d%d%d%d",&m,a,b,c,d,&p,&q,&r,&mod,&K);
    for(int i=1;i<=m;++i)
    {
        a[i&1]=(1LL*p*a[(i&1)^1]+1LL*q*b[(i&1)^1]+r)%mod;
        b[i&1]=(1LL*p*b[(i&1)^1]+1LL*q*a[(i&1)^1]+r)%mod;
        c[i&1]=(1LL*p*c[(i&1)^1]+1LL*q*d[(i&1)^1]+r)%mod;
        d[i&1]=(1LL*p*d[(i&1)^1]+1LL*q*c[(i&1)^1]+r)%mod;
        rec[i].xl=min(a[i&1]%n,b[i&1]%n)+1;
        rec[i].xr=max(a[i&1]%n,b[i&1]%n)+1;
        rec[i].yl=min(c[i&1]%n,d[i&1]%n)+1;
        rec[i].yr=max(c[i&1]%n,d[i&1]%n)+1;
        rec[i].o=i;
        mn[i]=INF;
        mx[i]=-INF;
        prod[i]=1;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            val[i]=make_pair(x,y);
        }
        build(1,1,n);
        read();
        solve(1,n,1,m);
        long long ans=0;
        for(int i=1;i<=m;++i)
        if(mn[i]!=INF)
            ans+=prod[i]^mx[i]^mn[i];
        printf("%lld\n",ans);
    }
    return 0;
}

 

高维前缀和

问题的引入

一个二维矩阵的前缀和,一般来说定义为。

代码常见的写法就是用容斥加加减减:

for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
        S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[[i][j];

这是二维的情况,如果是三维或者是更高的k维,不难发现复杂度有一个,指数爆炸了。

然而,用高维前缀和的技巧,就可以有效的将时间复杂度降下来。具体的思路是一维一维的求和。比如还是刚才二维的例子,为方便叙述,想象矩阵左上角是,我们先对每行分别从左到右累加,即对每行求一维前缀和,再对每列从上到下累加,还是相同的过程,这样求出的结果就是二维前缀和了。也可以从定义前缀和的式子入手考虑,每个求和号就代表一个维度,我们的计算过程就相当于一个求和号一个求和号的算,比较简单。

高维前缀和代码,简洁的一匹:

for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
        S[i][j]=A[i][j];

for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
        S[i][j]+=S[i][j-1];
for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
        S[i][j]+=S[i-1][j];

子集和变换

高维前缀和在二进制数上的应用就是做子集和变换。比如有一些小于正整数给一个数x,我要统计所有满足的数y有多少个,这里的and就是二进制与。这里其实还是高维前缀和,可以把每一个数看成20维超立方体的其中一个格子,满足上述式子的x和y的关系就是,每一个维度下y对应的值都要小于等于x对应的值(虽然每个维度只有两种值,0或1)这样就是相同的问题了,于是我们不仅可以维护一个子集的信息,还可以维护超集的信息,维护的内容也不只限于求和,还可以求最值等等。

求超集和:

void doit(int *f,int n)
{
    int len=1<<n;
    for(int i=0;i<n;++i)
        for(int j=0;j<len;++j)
            if(~j&(1<<i))
                f[j]+=f[j^(1<<i)];
}

第一层循环枚举维度,第二层枚举所有元素,注意第二层循环正序或者倒序都是一样的,因为每个维度大小只有2,即0或1,做的就是把“1”加到“0”上。

练习题目

1.SPOJ Time Limit Exceeded

简单的递推一下就是记表示考虑前i个数,第i个数为j的方案数,转移方程很容易,并且如果j是的倍数,那么。

然而朴素的转移是,显然会TLE。转化一下等价于,那么我们把上一次的dp值状态取反,然后求超集和就ok了,时间复杂度。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9;
#define N 55
#define M 16
int n,m;
int c[N];
int dp[1<<M];
void doit(int *f,int n)
{
    int len=1<<n;
    for(int i=0;i<n;++i)
        for(int j=0;j<len;++j)
            if(~j&(1<<i))
                f[j]=(f[j]+f[j^(1<<i)])%mod;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) scanf("%d",c+i);
        int len=1<<m;
        for(int i=1;i<len;++i)dp[i]=0;
        dp[0]=1;
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<len;j+=2) swap(dp[j],dp[j^(len-1)]);
            doit(dp,m);
            for(int j=0;j<len;j+=c[i]) dp[j]=0;
        }
        int ans=0;
        for(int i=0;i<len;++i) ans=(ans+dp[i])%mod;
        printf("%d\n",ans);
    }
}

2.codeforces 449D – Jzzhu and Numbers

求and起来为0的子集的个数。

先用高维前缀和算出表示状态包含S的数的个数,然后令就是and起来包含S的子集的个数,然后再高维差分回去,就能求出答案了。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n;
int dp[1<<20];
int power(int x,int n)
{
    int ans=1;
    while(n)
    {
        if(n&1) ans=1LL*ans*x%mod;
        x=1LL*x*x%mod;
        n>>=1;
    }
    return ans;
}
void doit(int *f,int n,int o)
{
    int len=1<<n;
    for(int i=0;i<n;++i)
        for(int j=0;j<len;++j)
            if(~j&(1<<i))
                f[j]=(f[j]+f[j^(1<<i)]*o)%mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        int x;
        scanf("%d",&x);
        dp[x]++;
    }
    doit(dp,20,1);
    for(int i=0;i<(1<<20);++i) dp[i]=power(2,dp[i]);
    doit(dp,20,-1);
    printf("%d\n",(dp[0]+mod)%mod);
    return 0;
}

3.hihocoder 1496 寻找最大值

求的最大值,枚举&值,前面就选超集中的最大值和次大值,用高维前缀和处理出来。

#include<bits/stdc++.h>
using namespace std;
int n;
int f[1<<20];
int g[1<<20];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int len=1<<20;
        for(int i=0;i<len;++i) f[i]=g[i]=0;
        for(int i=1;i<=n;++i)
        {
            int x;
            scanf("%d",&x);
            if(f[x]) g[x]=x;
            f[x]=x;
        }
        for(int i=0;i<20;++i)
            for(int j=0;j<len;++j)
                if((~j)&(1<<i))
                {
                    int k=j^(1<<i);
                    if(f[k]>f[j])
                    {
                        g[j]=max(f[j],g[k]);
                        f[j]=f[k];
                    }
                    else g[j]=max(g[j],f[k]);
                }
        long long ans=0;
        for(int i=0;i<len;++i)
            ans=max(ans,1LL*f[i]*g[i]*i);
        printf("%lld\n",ans);
    }
    return 0;
}

4.2016 Multi-University Training Contest 4 Bonds

给一个不超过20个点的无向连通图,无重边无自环,求每条边被多少个极小割边集包括。

显然能观察到极小割只会将图分成两个连通块,那么我们先用点的连通性作为状态bfs一下,得到所有可能的分法。之后如果暴力统计的话复杂度就是,我们计算反面,每条边极小割边集出出现的次数等于极小割总数减去这条边连接的两点在同一连通块的情况,然后就可以高维前缀和了,。

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
int bs[1<<21];
int q[1<<21];
int ans[1<<21];
bool vis[1<<21];
int n,m;
int a[400],b[400];
void bfs()
{
    int l=0,r=0;
    for(int i=0;i<n;++i)
        q[r++]=1<<i,vis[1<<i]=true;
    while(l!=r)
    {
        int x=q[l++];
        int y=bs[x]&(~x);
        while(y)
        {
            if(!vis[x|lowbit(y)])
            {
                vis[x|lowbit(y)]=true;
                q[r++]=x|lowbit(y);
            }
            y-=lowbit(y);
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;++cas)
    {
        scanf("%d%d",&n,&m);
        int all=1<<n;
        for(int i=0;i<all;++i) bs[i]=0,vis[i]=0,ans[i]=0;
        for(int i=1;i<=m;++i)
        {
            scanf("%d%d",a+i,b+i);
            bs[1<<a[i]]|=1<<b[i];
            bs[1<<b[i]]|=1<<a[i];
        }
        for(int i=0;i<all;++i)
            bs[i]=bs[i^lowbit(i)]|bs[lowbit(i)];
        bfs();
        int tot=0;
        for(int i=0;i<all;++i)
        if(i<((all-1)^i) && vis[i] && vis[(all-1)^i])
            ans[i]++,ans[(all-1)^i]++,tot++;
        for(int i=0;i<n;++i)
            for(int j=0;j<all;++j)
                if(~j&(1<<i))
                    ans[j]+=ans[j^(1<<i)];
        printf("Case #%d:",cas);
        for(int i=1;i<=m;++i)
            printf(" %d",tot-ans[(1<<a[i])|(1<<b[i])]);
        puts("");
    }
    return 0;
}

5.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest F.GCD

先从n个数中随机一个数,然后就有大于二分之一的概率选到了最优解中的一个数,那么枚举这个数的所有约数,用至少是n-k个数的约数的数更新答案,重复多做几次,降低随不到的概率。关键是怎么不暴力的做后面说的这个事情。首先,一个范围内的数的约数个数不会很多,大概几倍的就够,这个可以等完写个搜索验证一下。然后将随到数分解质因数,每个不同的质因数看成一个维度,然后求个高维后缀和,就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
int prime[1000010],tot;
bool vis[1000010];
ll a[N],ans;
int n,k;
void getprime()
{
    for(int i=2;i<=1000000;++i)
    {
        if(!vis[i]) prime[++tot]=i;
        for(int j=1;j<=tot && prime[j]<=1000000/i;++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
ll p[50];
int num[50];
int cnt;
ll dv[5000010];
int f[5000010];
int len;
void dfs(int x,ll now)
{
    if(x>cnt)
    {
        dv[++len]=now;
        return;
    }
    dfs(x+1,now);
    for(int i=1;i<=num[x];++i)
    {
        now*=p[x];
        dfs(x+1,now);
    }
}

void divide(ll x)
{
    for(int i=1;i<=tot;++i)
    if(x%prime[i]==0)
    {
        ++cnt;
        p[cnt]=prime[i];
        num[cnt]=0;
        while(x%prime[i]==0)
            x/=prime[i],++num[cnt];
    }
    for(int i=1;i<=n;++i)
    {
        ll g=__gcd(x,a[i]);
        if(g>1 && g<x)
        {
            if(g==x/g) ++cnt,p[cnt]=g,num[cnt]=2;
            else
            {
                p[++cnt]=g;num[cnt]=1;
                p[++cnt]=x/g;num[cnt]=1;
                if(p[cnt-1]>p[cnt]) swap(p[cnt-1],p[cnt]);
            }
            x=1;
            break;
        }
    }
    if(x>1) p[++cnt]=x,num[cnt]=1;
}
void work(ll now)
{
    cnt=len=0;
    divide(now);
    dfs(1,1);
    sort(dv+1,dv+len+1);
    for(int i=1;i<=len;++i) f[i]=0;
    for(int i=1;i<=n;++i)
    {
        ll g=__gcd(now,a[i]);
        ++f[lower_bound(dv+1,dv+len+1,g)-dv];
    }
    for(int i=1;i<=cnt;++i)
    {
        ll x=p[i];
        for(int j=len,k=len;j>=1;--j)
        if(dv[j]%x==0)
        {
            ll y=dv[j]/x;
            while(dv[k]>y) --k;
            f[k]+=f[j];
        }
    }
    for(int i=1;i<=len;++i)
        if(f[i]>=n-k)
            ans=max(ans,dv[i]);
}
int main()
{
    mt19937 rnd(time(0));
    getprime();
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%lld",a+i);
    ans=1;
    for(int i=1;i<=20;++i)
        work(a[rnd()%n+1]);
    printf("%lld\n",ans);
    return 0;
}

 

线段树优化凸壳

Lena and Queries

题目链接:http://codeforces.com/contest/678/problem/F

三种操作,1.插入一个点(x,y) 2.删除之前第i个操作插入的点 3.给一个q,询问在已有点中qx+y最大是多少

如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立,所以不能cdq分治。

但是可以用上一次线段树优化建图一样的技巧,按时间来看,因为每个点的存在是一段区间,那么就可以用线段树拆成log个区间,然后把点“打”在上面(加进vector),最后对于线段树上每个区间,做凸壳然后询问就行了。每个询问会被问log次,所以时间复杂度粗略算有。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
const ll NINF=1LL<<63;
struct Point
{
    ll x,y;
    Point(){}
    Point(ll x_,ll y_)
    {
        x=x_;
        y=y_;
    }
    Point operator -(const Point &t)const
    {
        return Point(x-t.x,y-t.y);
    }
    ll operator *(const Point &t)const
    {
        return x*t.x+y*t.y;
    }
    ll operator ^(const Point &t)const
    {
        return x*t.y-t.x*y;
    }
    bool operator <(const Point &t)const
    {
        return x<t.x||(x==t.x && y<t.y);
    }
} p[N],res[N];
vector<Point> v[N<<2];
int opt[N];
bool del[N],emp[N];
int n,top;
ll ans[N];
void insert(int o,int l,int r,int ql,int qr,int x)
{
    if(ql<=l && r<=qr)
    {
        v[o].push_back(p[x]);
        return;
    }
    int mid=l+r>>1;
    if(ql<=mid) insert(o<<1,l,mid,ql,qr,x);
    if(mid<qr) insert(o<<1|1,mid+1,r,ql,qr,x);
}
void ask(int o)
{
    int l=1,r=top;
    while(r-l>=3)
    {
        int x=(l*2+r)/3;
        int y=(l+2*r)/3;
        if(p[o]*res[x]<p[o]*res[y]) l=x;
        else r=y;
    }
    for(int i=l;i<=r;++i)
        ans[o]=max(ans[o],p[o]*res[i]);
}
void solve(int o,int l,int r)
{
    if(l<r)
    {
        int mid=l+r>>1;
        solve(o<<1,l,mid);
        solve(o<<1|1,mid+1,r);
    }
    sort(v[o].begin(),v[o].end());
    top=0;
    //cout<<o<<" "<<l<<" "<<r<<" "<<v[o].size()<<endl;
    for(int i=0;i<v[o].size();++i)
    {
        while(top>1 && ((res[top]-res[top-1])^(v[o][i]-res[top]))>=0) --top;
        res[++top]=v[o][i];
    }
    for(int i=l;i<=r;++i)
        if(opt[i]==3 && !emp[i])
        {
            //cout<<"ask"<<endl;
            ask(i);
            //cout<<ans[i]<<endl;
        }
}
int main()
{
    scanf("%d",&n);
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&opt[i]);
        if(opt[i]==1)
        {
            scanf("%lld%lld",&p[i].x,&p[i].y);
            ++cnt;
        }
        else if(opt[i]==2)
        {
            int x;
            scanf("%d",&x);
            del[x]=true;
            --cnt;
            insert(1,1,n,x,i-1,x);
        }
        else
        {
            scanf("%lld",&p[i].x);
            p[i].y=1;
            if(cnt==0) emp[i]=true;
        }
    }
    for(int i=1;i<=n;++i)
        if(opt[i]==1 && !del[i])
            insert(1,1,n,i,n,i);
    for(int i=1;i<=n;++i) ans[i]=NINF;

    solve(1,1,n);
    for(int i=1;i<=n;++i)
    if(opt[i]==3)
    {
        if(emp[i]) printf("EMPTY SET\n");
        else printf("%lld\n",ans[i]);
    }
    return 0;
}
/*
3
1 -1 0
1 -1 1
3 -2
*/

 

 

2018 CCPC网络赛 GuGu Convolution

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442

定义序列

它的指数型生成函数为

设是一个常数

定义序列,

定义两个生成函数的卷积(原题面省略了阶乘,可能是写错了?)

现在给三个正整数,求的前的系数乘上后的结果

赛中走了很多弯路,思路大概是这样的

首先用泰勒展开,可以看出

所以

第n项系数为

类似斐波那契数列也可以强行求出线性递推的式子然后矩阵快速幂,就是推得比较难受罢了==

更快的方法

不用泰勒展开,直接用二项式定理类似的凑一下就可以得到第n项系数的式子,最后也不用推递推式,答案就是中去掉整数项x,直接快速幂就做完了。

赛中代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,n,mod;
struct matrix
{
    ll mx[2][2];
    matrix()
    {
        memset(mx,0,sizeof(mx));
    }
    void clear()
    {
        memset(mx,0,sizeof(mx));
    }
    void init()
    {
        memset(mx,0,sizeof(mx));
        mx[0][0]=mx[1][1]=1;
    }
    friend matrix operator *(const matrix &a,const matrix &b)
    {
        matrix c;
        for(int i=0;i<2;++i)
            for(int k=0;k<2;++k)
                for(int j=0;j<2;++j)
                    c.mx[i][j]=(c.mx[i][j]+a.mx[i][k]*b.mx[k][j])%mod;
        return c;
    }
}A,ans;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&mod);
        ans.init();
        A.mx[0][0]=2*a%mod;A.mx[0][1]=1;
        A.mx[1][0]=(b-a*a%mod+mod)%mod;A.mx[1][1]=0;
        --n;
        while(n)
        {
            if(n&1) ans=ans*A;
            A=A*A;
            n>>=1;
        }
        ll pp=0;
        for(ll i=1;1LL*i*i<=b;++i)
        if(b%(i*i)==0)
            pp=i;
        printf("%d %I64d %I64d\n",1,ans.mx[0][0]*pp%mod,b/(pp*pp));
    }
}

 

线段树优化建图

有一类经典的问题,之前见过很多次了,好像某一场区域赛的热身赛里就出过:一维数轴上有n个炸弹,分别表示第i个炸弹的位置和引爆半径,即如果引爆炸弹i,那么位置在范围内的炸弹都会爆炸,并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。

首先一个建图思路是如果i能引爆j,那么i向j连一条边,做tarjan求强连通分量就可以知道很多信息了。但是这样暴力连边是的,需要优化。一个显然的观察是,一个点i的引爆范围是一段区间(这句是废话),所以是和一个区间的点连边,那么我们把炸弹按位置排序后,1到n编好号,建线段树,线段树每个点向左右儿子分别连边。如果i要向区间(l,r)所有点连边的话,就在线段树中将区间(l,r)分解成条线段,这样就转化成了向对应的线段树中的一些点连边,总的边数就是。

来看两道具体的题目:

bzoj 5017 [Snoi2017]炸弹

询问如果把第 i 个炸弹引爆,将引爆多少个炸弹。

线段树优化建图,然后tarjan,答案是从i所在的SCC出发,能走到的SCC含有的原炸弹数之和。因为对于每个i都要询问,所以这里不能暴力,一个方法是在这个DAG的反图上拓扑序dp一下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 2000010
#define M 11000010
const ll mod=1e9+7;
const ll mod2=mod*mod;
struct node
{
    ll x,r;
} a[N];
ll pos[N];
int tot,rt,n;
int ls[N],rs[N];
int e,head[M],last[M],p[N];
int dfn[N],low[N],sta[N],color[N],val[N];
int in[N],q[N];
bool v[N];
int dfstime,num,siz,len;
vector<int> redge[N];
pair<int,int> pr[M];
bool cmp(const node &a,const node &b)
{
    return a.x<b.x;
}
void add(int x,int y)
{
    head[++e]=y;
    last[e]=p[x];
    p[x]=e;
}
void build(int &x,int l,int r)
{
    x=(l==r)?l:(++tot);
    if(l==r) return;
    int mid=l+r>>1;
    build(ls[x],l,mid);
    build(rs[x],mid+1,r);
    add(x,ls[x]);
    add(x,rs[x]);
}
void ins(int x,int l,int r,int L,int R,int y)
{
    if(L<=l && r<=R)
    {
        add(y,x);
        return;
    }
    int mid=l+r>>1;
    if(L<=mid) ins(ls[x],l,mid,L,R,y);
    if(mid<R) ins(rs[x],mid+1,r,L,R,y);
}
void tarjan(int x)
{
    int y;
    dfn[x]=low[x]=++dfstime;
    sta[++siz]=x;
    v[x]=true;
    for(int j=p[x];j;j=last[j])
        if(!dfn[y=head[j]])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y])
            low[x]=min(low[x],dfn[y]);
    if(low[x]==dfn[x])
    {
        ++num;
        do
        {
            y=sta[siz--];
            color[y]=num;
            v[y]=false;
        }while(y!=x);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&a[i].x,&a[i].r);
        pos[i]=a[i].x;
    }
    tot=n;
    build(rt,1,n);
    for(int i=1;i<=n;++i)
    {
        int l=lower_bound(pos+1,pos+n+1,a[i].x-a[i].r)-pos;
        int r=upper_bound(pos+1,pos+n+1,a[i].x+a[i].r)-pos-1;
        ins(rt,1,n,l,r,i);
    }
    for(int i=1;i<=tot;++i)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;++i)
        val[color[i]]++;
    for(int x=1;x<=tot;++x)
    {
        for(int j=p[x];j;j=last[j])
        {
            int y=head[j];
            if(color[x]==color[y]) continue;
            pr[++len]=make_pair(color[y],color[x]);
        }
    }
    sort(pr+1,pr+len+1);
    len=unique(pr+1,pr+len+1)-pr-1;
    for(int i=1;i<=len;++i)
    {
        redge[pr[i].first].push_back(pr[i].second);
        ++in[pr[i].second];
    }
    int l=0,r=0;
    for(int i=1;i<=num;++i)
        if(!in[i])
            q[r++]=i;
    while(l!=r)
    {
        int x=q[l++];
        for(int i=0;i<redge[x].size();++i)
        {
            int y=redge[x][i];
            val[y]+=val[x];
            if((--in[y])==0) q[r++]=y;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        ans+=1LL*i*val[color[i]];
        if(ans>=mod2) ans-=mod2;
    }
    ans%=mod;
    printf("%d\n",ans);
}

 

Petrozavodsk Winter-2018. Carnegie Mellon U Contest A Mines

现在每个炸弹多了一个初始的引爆费用,因为连锁发生的爆炸是免费的。有q次修改,每次修改一个炸弹的费用,对于每次修改都要查询当前要引爆所有炸弹的最小花费。

前面的操作都一样,首先一个显然的想法是只要引爆DAG中所有入度为0的SCC里的费用最小的炸弹。然后有个致命的问题是,入度为0的SCC可能不含有原1到n号点,所以需要做拓扑排序删掉没用的点,之后对于每次询问用set维护即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define NN 200010
#define N 800010
#define M 16000010
#define rep(i,l,r) for(int i=l;i<=r;++i)
struct node
{
    int x,r,c,o;
} a[NN];
int h[NN],pos[NN],ls[N],rs[N];
int n,tot,m,rt,dfstime,siz,num;
int e,head[M],last[M],p[N];
int dfn[N],low[N],sta[N],color[N];
int in[N],q[N];
bool v[N],ok[N];
vector<int> edge[N];
multiset<int> st[N];
bool cmp(const node &a,const node &b)
{
    return a.x<b.x;
}

void add(int x,int y)
{
    head[++e]=y;
    last[e]=p[x];
    p[x]=e;
}
void tarjan(int x)
{
    int y;
    dfn[x]=low[x]=++dfstime;
    sta[++siz]=x;
    v[x]=true;
    for(int j=p[x];j;j=last[j])
        if(!dfn[y=head[j]])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y])
            low[x]=min(low[x],dfn[y]);
    if(low[x]==dfn[x])
    {
        ++num;
        do
        {
            y=sta[siz--];
            color[y]=num;
            v[y]=false;
        }while(y!=x);
    }
}
void build(int &x,int l,int r)
{
    x=(l==r)?l:(++tot);
    if(l==r) return;
    int mid=l+r>>1;
    build(ls[x],l,mid);
    build(rs[x],mid+1,r);
    add(x,ls[x]);
    add(x,rs[x]);
}
void ins(int x,int l,int r,int L,int R,int y)
{
    if(L<=l && r<=R)
    {
        add(y,x);
        return;
    }
    int mid=l+r>>1;
    if(L<=mid) ins(ls[x],l,mid,L,R,y);
    if(mid<R) ins(rs[x],mid+1,r,L,R,y);
}
int main()
{
    #ifdef SK
    freopen("input.txt","r",stdin);
    #endif // SK
    scanf("%d%d",&n,&m);
    rep(i,1,n)
    {
        scanf("%d%d%d",&a[i].x,&a[i].r,&a[i].c);
        a[i].o=i;
    }
    sort(a+1,a+n+1,cmp);
    rep(i,1,n) h[i]=a[i].x,pos[a[i].o]=i;
    tot=n;
    build(rt,1,n);
    rep(i,1,n)
    {
        int l=lower_bound(h+1,h+n+1,a[i].x-a[i].r)-h;
        int r=upper_bound(h+1,h+n+1,a[i].x+a[i].r)-h-1;
        ins(rt,1,n,l,r,i);
    }
    rep(i,1,tot)
        if(!dfn[i])
            tarjan(i);
    rep(i,1,n) ok[color[i]]=true;
    for(int x=1;x<=tot;++x)
    {
        for(int j=p[x];j;j=last[j])
        {
            int y=head[j];
            int xx=color[x],yy=color[y];
            if(xx==yy) continue;
            edge[xx].push_back(yy);
            ++in[yy];
        }
    }
    int l=0,r=0;
    rep(i,1,num)
        if(!in[i] && !ok[i])
            q[r++]=i;
    while(l!=r)
    {
        int x=q[l++];
        for(auto &y:edge[x])
        {
            --in[y];
            if(!in[y] && !ok[y]) q[r++]=y;
        }
    }

    rep(i,1,n)
        if(!in[color[i]])
            st[color[i]].insert(a[i].c);

    ll ans=0;
    rep(i,1,num)
        if(ok[i] && !in[i] && !st[i].empty())
            ans+=*st[i].begin();

    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x=pos[x];
        if(!in[color[x]])
        {
            ans-=*st[color[x]].begin();
            auto it=st[color[x]].find(a[x].c);
            st[color[x]].erase(it);
            a[x].c=y;
            st[color[x]].insert(a[x].c);
            ans+=*st[color[x]].begin();
        }
        printf("%lld\n",ans);
    }
    return 0;
}

 

NOIP 2014

题目链接:https://vijos.org/p/category/2014

D1T1 生活大爆炸版 石头剪刀布

没想到noip还会出纯模拟

#include<bits/stdc++.h>
using namespace std;
#define N 205
#define rep(i,l,r) for(int i=l;i<=r;++i)
int n,na,nb;
int a[N],b[N];
const int w[5][5]={{0,-1,1,1,-1},{1,0,-1,1,-1},{-1,1,0,-1,1},{-1,-1,1,0,1},{1,1,-1,-1,0}};
int main()
{
    while(scanf("%d%d%d",&n,&na,&nb)!=EOF)
    {
        rep(i,0,na-1) scanf("%d",a+i);
        rep(i,0,nb-1) scanf("%d",b+i);
        int ans1=0,ans2=0;
        rep(i,0,n-1)
        {
            int x=a[i%na],y=b[i%nb];
            if(w[x][y]>0) ++ans1;
            else if(w[x][y]<0) ++ans2;
        }
        printf("%d %d\n",ans1,ans2);
    }
}

D1T2 联合权值 

dfs一下就统计出来了

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
#define N 200010
#define rep(i,l,r) for(int i=l;i<=r;++i)
int e,head[N<<1],last[N<<1],p[N];
int deep[N];
int a[N];
int sum[N],md[N];
int ans1,ans2;
int n;
void add(int &x,int y)
{
    (x+=y)>=mod && (x-=mod);
}
void addedge(int x,int y)
{
    head[++e]=y;
    last[e]=p[x];
    p[x]=e;
}
void dfs(int x,int pre,int dep)
{
    deep[x]=dep;
    sum[x]=0;
    md[x]=0;
    int now=0,ss=0,mm=0;
    int max1=0,max2=0;
    for(int j=p[x];j;j=last[j])
    {
        int y=head[j];
        if(y==pre) continue;
        dfs(y,x,dep+1);
        add(sum[x],a[y]);
        add(now,a[y]*a[y]%mod);
        add(ss,sum[y]);
        md[x]=max(md[x],a[y]);
        mm=max(mm,md[y]);
        if(a[y]>=max1) max2=max1,max1=a[y];
        else max2=max(max2,a[y]);
    }
    add(ans2,2*ss*a[x]%mod);
    add(ans2,(sum[x]*sum[x]-now+mod)%mod);
    ans1=max(ans1,mm*a[x]);
    ans1=max(ans1,max1*max2);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        e=0;
        memset(p,0,sizeof(p));
        memset(md,0,sizeof(md));
        memset(sum,0,sizeof(sum));
        rep(i,1,n-1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
        }
        rep(i,1,n) scanf("%d",a+i);
        ans1=0,ans2=0;
        dfs(1,0,1);
        printf("%d %d\n",ans1,ans2);
    }
}

D1T3  飞扬的小鸟

这个dp有、东西,日常不会dp

#include<bits/stdc++.h>
using namespace std;
#define N 10010
#define M 1010
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int INF=0x3f3f3f3f;
bool wall[N];
vector<int> now,las;
int n,m,q;
int a[N],b[N];
int l[N],r[N];
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    rep(i,0,n-1)
    {
        scanf("%d%d",a+i,b+i);
        l[i]=0;
        r[i]=m+1;
    }
    l[n]=0;r[n]=m+1;
    rep(i,1,q)
    {
        int x;
        scanf("%d",&x);
        scanf("%d%d",&l[x],&r[x]);
        wall[x]=true;
    }

    now.resize(m+5);
    las.resize(m+5);
    rep(i,1,m) las[i]=0;
    las[0]=INF;
    int ans1=INF,ans2=0;
    rep(i,1,n)
    {
        int x=a[i-1];
        rep(j,0,m) now[j]=INF;
        rep(j,x,m)
        {
            now[j]=min(now[j],las[j-x]+1);
            now[j]=min(now[j],now[j-x]+1);
        }
        rep(j,m-x,m)
        {
            now[m]=min(now[m],las[j]+1);
            now[m]=min(now[m],now[j]+1);
        }
        rep(j,l[i]+1,r[i]-1)
        if(j+b[i-1]<=m)
            now[j]=min(now[j],las[j+b[i-1]]);
        rep(j,0,l[i]) now[j]=INF;
        rep(j,r[i],m) now[j]=INF;
        if(wall[i])
        rep(j,l[i]+1,r[i]-1)
            if(now[j]<INF)
            {
                ++ans2;
                break;
            }
        swap(now,las);
    }
    rep(j,1,m) ans1=min(ans1,las[j]);
    if(ans1<INF)
    {
        puts("1");
        printf("%d\n",ans1);
    }
    else
    {
        puts("0");
        printf("%d\n",ans2);
    }
}

 

D2T1 无线网络发射器选址  

记前缀和,然后枚举

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
int n,d;
int a[130][130];
int main()
{
    scanf("%d",&d);
    scanf("%d",&n);
    rep(i,1,n)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        ++x;++y;
        a[x][y]+=c;
    }
    int ans1=0,ans2=0;
    rep(i,1,129)
        rep(j,1,129)
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    rep(i,1,129)
        rep(j,1,129)
        {
            int x=min(129,i+d);
            int y=min(129,j+d);
            int xx=max(0,i-d-1);
            int yy=max(0,j-d-1);
            int now=a[x][y]-a[x][yy]-a[xx][y]+a[xx][yy];
            if(now>ans2) ans1=1,ans2=now;
            else if(now==ans2) ++ans1;
        }
    printf("%d %d\n",ans1,ans2);
}

D2T2 寻找道路

先在反图上从终点bfs,求出哪些点能到终点,然后从起点正着按题意bfs就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 10010
#define M 200010
vector<int> edge[N];
vector<int> redge[N];
queue<int> q;
bool vis[N];
bool ok[N];
int dis[N];
int n,m;
void pre(int s)
{
    vis[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto &y:redge[x])
        if(!vis[y])
        {
            vis[y]=true;
            q.push(y);
        }
    }
}
int bfs(int st,int ed)
{
    if(!ok[st]) return -1;
    memset(dis,-1,sizeof(dis));
    dis[st]=0;
    q.push(st);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto &y:edge[x])
        if(ok[y] && dis[y]==-1)
        {
            dis[y]=dis[x]+1;
            q.push(y);
        }
    }
    return dis[ed];
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,m)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        redge[y].push_back(x);
        edge[x].push_back(y);
    }
    int st,ed;
    scanf("%d%d",&st,&ed);
    pre(ed);
    memset(ok,true,sizeof(ok));
    rep(y,1,n)
    if(!vis[y])
        for(auto &x:redge[y])
            ok[x]=false;
    printf("%d\n",bfs(st,ed));
}

D2T3 解方程

直接解肯定没办法,只能枚举答案,然后随机素数取模验证。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 1000010
char s[105][10010];
int val[105][205];
int f[20000][10];
bool ok[N];
const int prime[]={19997,19961,19759,18013,17011,15359};
const int tot=6;
int n,m;

int calc(char *s,int mod)
{
    int now=0;
    for(int i=(s[0]=='-')?1:0;s[i];++i)
        now=(1LL*now*10+s[i]-'0')%mod;
    if(s[0]=='-') now=(mod-now)%mod;
    return now;
}
int check(int x,int y,int mod)
{
    int now=1,ans=0;
    rep(i,0,n)
    {
        ans+=1LL*val[i][y]*now%mod;
        if(ans>=mod) ans-=mod;
        now=1LL*now*x%mod;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    rep(i,0,n)
    {
        scanf("%s",s[i]);
        rep(j,0,tot-1) val[i][j]=calc(s[i],prime[j]);
    }
    rep(i,1,m) ok[i]=true;
    int ans=0;
    rep(i,0,m)
    if(ok[i])
    {
        for(int j=0;j<tot;++j)
        {
            if(i<prime[j]) f[i][j]=check(i,j,prime[j]);
            if(f[i%prime[j]][j]) ok[i]=false;
        }
        if(i>0 && ok[i]) ++ans;
    }
    printf("%d\n",ans);
    rep(i,1,m) if(ok[i]) printf("%d\n",i);
}

 

 

NOIP 2013

最近突然想回顾一下历年noip题目,就开个新坑吧,题解就从略了

题目链接 https://vijos.org/p/category/2013

D1T1 转圈游戏

公式就,现在一眼的事情当时想了很久orz

#include<bits/stdc++.h>
using namespace std;
int power(int x,int n,int mod)
{
    int ans=1;
    while(n)
    {
        if(n&1) ans=1LL*ans*x%mod;
        x=1LL*x*x%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    int n,m,k,x;
    while(scanf("%d%d%d%d",&n,&m,&k,&x)!=EOF)
    {
        int ans=(x+1LL*m*power(10,k,n))%n;
        printf("%d\n",ans);
    }
}

D1T2 火柴排队

首先肯定是小对小,大对大,才能使那个式子最小,这一点可以交换一下然后做差说明。并且题目保证了高度互不相同,也就是给了两个排列,问最少交换相邻元素多少次,才能使两个排列一样,再转化一步,假设第一个排列就是1,2,3,…n,问第二个排列最少交换相邻元素几次才能变成1,2,3,…n,这就是逆序对的定义了。

不知道如果不保证高度互不相同该怎么做orz

当时这个题爆零了,一点也不会QAQ

#include<bits/stdc++.h>
using namespace std;
const int mod=99999997;
#define N 100010
#define rep(i,l,r) for(int i=l;i<=r;++i)

int a[N],b[N],h[N];
int c[N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
int ask(int x)
{
    int ans=0;
    for(;x<=n;x+=lowbit(x))
        ans+=c[x];
    return ans;
}
void change(int x,int y)
{
    for(;x;x-=lowbit(x))
        c[x]+=y;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        rep(i,1,n) scanf("%d",a+i),h[i]=a[i];
        sort(h+1,h+n+1);
        rep(i,1,n) a[i]=lower_bound(h+1,h+n+1,a[i])-h;
        rep(i,1,n) scanf("%d",b+i),h[i]=b[i];
        sort(h+1,h+n+1);
        rep(i,1,n) b[i]=lower_bound(h+1,h+n+1,b[i])-h;

        rep(i,1,n) h[a[i]]=i;
        rep(i,1,n) b[i]=h[b[i]],c[i]=0;
        int ans=0;
        rep(i,1,n)
        {
            change(b[i],1);
            ans+=ask(b[i]+1);
            if(ans>=mod) ans-=mod;
        }
        printf("%d\n",ans);
    }
}

 

D1T3 货车运输

这个不难看出是最大生成树上倍增求路径边权最小值。要注意的是可能是一个森林,当时蠢的用tarjan判连通性了,强行增加码量。还好在赛前刚给别人讲过倍增,这题满分了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define dow(i,l,r) for(int i=l;i>=r;--i)
#define N 10010
#define M 50010
const int INF=0x3f3f3f3f;
struct edge
{
    int x,y,c;
} t[M];
int n,m,q;
int fa[N];
bool root[N];
bool cmp(const edge &a,const edge &b)
{
    return a.c>b.c;
}
int getfa(int x)
{
    return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
bool Union(int x,int y)
{
    x=getfa(x);
    y=getfa(y);
    if(x==y) return false;
    fa[x]=y;
    return true;
}
namespace TREE
{
int e,head[M<<1],last[M<<1],w[M<<1],p[N];
int f[N][21],g[N][21];
int deep[N];
void add(int x,int y,int c)
{
    head[++e]=y;w[e]=c;
    last[e]=p[x];
    p[x]=e;
}
void dfs(int x,int pre,int dep)
{
    deep[x]=dep;
    for(int j=p[x];j;j=last[j])
    {
        int y=head[j];
        if(y==pre) continue;
        f[y][0]=x;
        g[y][0]=w[j];
        rep(i,1,20)
        {
            f[y][i]=f[f[y][i-1]][i-1];
            g[y][i]=min(g[y][i-1],g[f[y][i-1]][i-1]);
        }
        dfs(y,x,dep+1);
    }
}
int askmax(int x,int y)
{
    if(deep[x]>deep[y]) swap(x,y);
    int ans=INF;
    dow(i,20,0)
        if(deep[f[y][i]]>=deep[x])
            ans=min(ans,g[y][i]),y=f[y][i];
    if(x==y) return ans;
    dow(i,20,0)
        if(f[x][i]!=f[y][i])
        {
            ans=min({ans,g[x][i],g[y][i]});
            x=f[x][i],y=f[y][i];
        }
    ans=min({ans,g[x][0],g[y][0]});
    return ans;
}

}//TREE

int main()
{
    scanf("%d%d",&n,&m);
    rep(i,1,m)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        t[i]=edge{x,y,c};
    }
    sort(t+1,t+m+1,cmp);
    rep(i,1,n) fa[i]=i;
    rep(i,1,m)
    {
        int x=t[i].x;
        int y=t[i].y;
        int c=t[i].c;
        if(Union(x,y))
        {
            TREE::add(x,y,c);
            TREE::add(y,x,c);
        }
    }
    rep(i,1,n) root[getfa(i)]=true;
    memset(TREE::g,INF,sizeof(TREE::g));
    rep(i,1,n)
        if(root[i])
            TREE::dfs(i,0,1);

    scanf("%d",&q);
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(getfa(x)!=getfa(y)) puts("-1");
        else printf("%d\n",TREE::askmax(x,y));
    }
}

D2T1 积木大赛

可能太简单,这题没什么印象了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 100010
int n;
int h[N];
int main()
{
    scanf("%d",&n);
    int ans=0;
    rep(i,1,n)
    {
        scanf("%d",h+i);
        ans+=max(0,h[i]-h[i-1]);
    }
    printf("%d\n",ans);
}

D2T2  花匠

当时从最长上升子序列的思路出发,然后推了推,写了个单调队列,具体怎么写的忘了,不过也是AC。实际上最简单的做法只需要扫一遍,求出拐点的个数,加2就是答案了。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define N 100010
int n;
int a[N];
int main()
{
    scanf("%d",&n);
    int ans=0;
    int now=0;
    rep(i,1,n)
    {
        scanf("%d",a+i);
        if(i==1||a[i-1]==a[i]) continue;
        if(a[i-1]<a[i])
        {
            if(now==-1) ++ans;
            now=1;
        }
        if(a[i-1]>a[i])
        {
            if(now==1) ++ans;
            now=-1;
        }
    }
    printf("%d\n",ans+2);
}

D2T3 华容道

这题xjb搜,就得了5分…

正确做法是bfs预处理,拆点,建图跑最短路。

具体来说:可以观察到只有空白块位于指定块的四方向上,指定块才可以移动。本质上还有另外一种移动方式,就是指定块不动,空白块从它的上/下左/右中的一个移动到另一个。那么这样就可以bfs预处理了,状态也有了,(x,y,k)表示指定块在(x,y),空白块在相邻的k方向上。spfa求最短路即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int INF=0x3f3f3f3f;
const int dx[]= {0,0,1,-1};
const int dy[]= {1,-1,0,0};
const int N=31*31*4;
const int M=4*N;
struct node
{
    int x,y;
} q[32*32*4];
int n,m,k;
int dis[32][32];
int can[32][32];

int e,head[M],last[M],w[M],p[N];
bool vis[N];
int dist[N];
bool ok(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<m && can[x][y];
}

void bfs(int sx,int sy)
{
    memset(dis,INF,sizeof(dis));
    dis[sx][sy]=0;
    int l=0,r=0;
    q[r++]=node{sx,sy};
    while(l!=r)
    {
        int x=q[l].x;
        int y=q[l].y;
        l++;
        rep(i,0,3)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(ok(xx,yy) && dis[xx][yy]==INF)
            {
                dis[xx][yy]=dis[x][y]+1;
                q[r++]=node{xx,yy};
            }
        }
    }
}
int calc(int x,int y,int k)
{
    return x*m*4+y*4+k;
}
void add(int x,int y,int c)
{
    head[++e]=y;
    w[e]=c;
    last[e]=p[x];
    p[x]=e;
}
void init()
{
    rep(i,0,n-1)
    rep(j,0,m-1)
    if(ok(i,j))
    {
        rep(k,0,3)
        {
            int x=i+dx[k];
            int y=j+dy[k];
            if(!ok(x,y)) continue;
            can[i][j]=0;
            bfs(x,y);
            can[i][j]=1;
            rep(h,0,3) if(h!=k)
            {
                int xx=i+dx[h];
                int yy=j+dy[h];
                if(ok(xx,yy) && dis[xx][yy]!=INF)
                    add(calc(i,j,k),calc(i,j,h),dis[xx][yy]);
            }
            add(calc(i,j,k),calc(x,y,k^1),1);
        }
    }
}
void spfa(int sx,int sy)
{
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(dist,INF,sizeof(dist));
    rep(i,0,3)
    if(ok(sx+dx[i],sy+dy[i]) && dis[sx+dx[i]][sy+dy[i]]!=INF)
    {
        int now=calc(sx,sy,i);
        dist[now]=dis[sx+dx[i]][sy+dy[i]];
        vis[now]=true;
        q.push(now);
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=false;
        for(int j=p[x]; j; j=last[j])
        {
            int y=head[j];
            if(dist[y]>dist[x]+w[j])
            {
                dist[y]=dist[x]+w[j];
                if(!vis[y])
                {
                    vis[y]=true;
                    q.push(y);
                }
            }
        }
    }
}
int work(int x,int y,int sx,int sy,int tx,int ty)
{
    if(sx==tx && sy==ty) return 0;
    can[sx][sy]=0;
    bfs(x,y);
    can[sx][sy]=1;
    spfa(sx,sy);
    int ans=INF;
    rep(i,0,3) ans=min(ans,dist[calc(tx,ty,i)]);
    if(ans==INF) ans=-1;
    return ans;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    rep(i,0,n-1)
    rep(j,0,m-1)
    scanf("%d",&can[i][j]);
    init();
    while(k--)
    {
        int x,y,sx,sy,tx,ty;
        scanf("%d%d%d%d%d%d",&x,&y,&sx,&sy,&tx,&ty);
        --x;--y;--sx;--sy;--tx;--ty;
        printf("%d\n",work(x,y,sx,sy,tx,ty));
    }
}
/*
3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2
*/

 

Dominator Tree

问题引入

题目要求解决的模型: 给定有向图G(可能有环)和图中的一个点r,对于G中的任意一个点x,求从r到x的路径上(可能有很多条)必须经过的点集。

  • Flow Graph:若有向图G中存在一点r,从r出发可到达G中所有的点,则称G是Flow Graph,记为(G,r)。
  • 必经点(dom):若在(G,r)中从r到y的路径一定经过点x,则称x是从r到达y的必经点,记为x dom y。 从r出发到达y的所有必经点构成的集合记为dom(y),即dom(y)={x | x dom y}。
  • 最近必经点(idom): 节点y的必经点集合dom(y)中dfn值最大的点x是距离y最近的必经点,称为y的最近必经点。最近必经点是唯一的,因此可以记x=idom(y)。

于是可以按下面暴力求解

  • y的前驱节点集合
  • x的后继节点集合

Dominator Tree

设有向图G=(V,E),(G,r)是一个Flow Graph,则称(G,r)的子图为(G,r)的一棵Dominator Tree。

(G,r)的Dominator Tree是一棵有向有根树,从r出发可以到达G中的所有点,并且树上的每条边(u,v)都满足:u=idom(v),即父节点是子节点的最近必经点。

  • x=idom(y),当且仅当有向边(x,y)是Dominator Tree中的一条树枝边。
  • x dom y,当且仅当在Dominator Tree中存在一条从x到y的路径。
  • x的必经点集合dom(x)是Dominator Tree上x的所有祖先以及x自身。

半必经点

半必经点(semi) 在搜索树T上点y的祖先中,经过时间戳比y大的节点可以到达y的深度最小的祖先x,称为y的半必经点。关于半必经点有如下性质:

  • 半必经点也是唯一的,因此可以记x=semi(y)。
  • 一个点的半必经点必定是它在dfs树上的祖先,dfn[semi[x]]<dfn[x]
  • 半必经点不一定是x的必经点。

如何求半必经点:对于G中一点y,考虑所有,设。

  • 若dfn[x]<dfn[y],则(x,y)为树枝边或前向边,此时
  • 若dfn[x]>dfn[y],则(x,y)为横叉边或后向边,此时任意x在T中的祖先z,满足dfn[z]>dfn[y]时,

必经点

对于G中的一点x,考虑搜索树T中semi(x)到x的路径上除端点之外的点构成的集合path

设,即path中半必经节点的时间戳最小的节点。

  • 时,
  • 时,

题目

1.hdu 4694 Important Sisters

给一个有向图,输出每个点的必经点集合里的点的编号和,源点是n

#include<bits/stdc++.h>
using namespace std;
#define N 500010
vector<int> edge[N],redge[N],edom[N];

int mn[N],dfn[N],idom[N],sdom[N],id[N],fa[N],f[N];
int cnt;

int find(int x)
{
    if(f[x]==x)return x;
    int y=find(f[x]);
    if(sdom[mn[x]]>sdom[mn[f[x]]])mn[x]=mn[f[x]];
    return  f[x]=y;
}
void dfs(int u)
{
    id[dfn[u]=++cnt]=u;
    for(auto &v:edge[u])
        if(!dfn[v])dfs(v),fa[dfn[v]]=dfn[u];
}
int n,m;
inline void tarjan(int s)
{
    for(int i=1; i<=n; i++)f[i]=sdom[i]=mn[i]=fa[i]=i,dfn[i]=0;
    cnt=0;
    dfs(s);
    int k,x;
    for(int i=cnt; i>1; i--)
    {
        for(auto &v:redge[id[i]])
            if(dfn[v])
                find(k=dfn[v]),sdom[i]= sdom[i]<sdom[mn[k]]?sdom[i]:sdom[mn[k]];
        edom[sdom[i]].push_back(i);
        f[i]=x=fa[i];
        for(auto &v:edom[x])
            find(k=v),idom[k] = sdom[mn[k]] < x?mn[k]:x;
        edom[x].clear();
    }
    for(int i=2; i<=cnt; i++)
    {
        if(idom[i]!=sdom[i])idom[i]=idom[idom[i]];
        edom[id[idom[i]]].push_back(id[i]);
        //if(idom[i]==i)puts("WA");
    }
}


int Ans[N];
void Mp(int u,int p)
{
    Ans[u]=p;
    for(auto &v:edom[u])
        Mp(v,p+v);
}


void out(int x)
{
    if(!x)
    {
        putchar('0');
        return ;
    }
    if(x>9)out(x/10);
    putchar('0'+x%10);
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        for(int i=1;i<=n;++i) edge[i].clear(),redge[i].clear(),edom[i].clear();
        for(int i=1; i<=m; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            edge[x].push_back(y);
            redge[y].push_back(x);
        }
        tarjan(n);
        Mp(n,n);
        for(int i=1; i<=n; i++)
            out(Ans[i]),putchar(i==n?'\n':' '),Ans[i]=0;
    }


    return 0;
}

2.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest L

无向图,边有边权,起点为1号点,记起点到点k的最短路为dk,询问如果增大输入中第i条边的边权,最短路会受到影响的点有多少个。

做法很自然,在最短路构成的DAG上求支配树,询问的就是支配树子树大小了。这里把边新建点,方便处理。

#include<bits/stdc++.h>
using namespace std;
#define N 400010
typedef long long ll;
int n,m,e;
int p[N],head[N],last[N],w[N];
bool vis[N];
ll dis[N];
int id[N],ans[N],num[N];
void add(int x,int y,int c)
{
    head[e]=y;w[e]=c;
    last[e]=p[x];
    p[x]=e++;
}
struct node
{
    int x;
    ll dis;
    node(){}
    node(int x_,ll dis_)
    {
        x=x_;
        dis=dis_;
    }
    bool operator <(const node &t)const
    {
        return dis>t.dis;
    }
};
priority_queue<node> q;
void dijkstra()
{
    for(int i=0;i<n;++i)
    {
        dis[i]=1LL<<60;
        vis[i]=0;
    }
    dis[0]=0;
    q.push(node(0,0));
    while(!q.empty())
    {
        int x=q.top().x;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int j=p[x];j!=-1;j=last[j])
        {
            int y=head[j];
            if(dis[y]>dis[x]+w[j])
            {
                dis[y]=dis[x]+w[j];
                q.push(node(y,dis[y]));
            }
        }
    }
}

int fa[N],nodeName[N],nodeID[N];

int ncnt=0;
vector<int> edge[N],redge[N];
void dfs(int x)
{
    vis[x]=true;
    nodeID[x]=ncnt;
    nodeName[ncnt++]=x;
    for(auto &y:edge[x])
    if(!vis[y])
    {
        fa[y]=x;
        dfs(y);
    }
}
int semi[N],idom[N],ufs[N];
int mnsemi[N];
vector<int> bucket[N];
int ufs_union(int x,int y)
{
    ufs[x]=y;
}
void ufs_internal_find(int x)
{
    if(ufs[ufs[x]]==ufs[x]) return;
    ufs_internal_find(ufs[x]);
    if(semi[mnsemi[ufs[x]]]<semi[mnsemi[x]])
        mnsemi[x]=mnsemi[ufs[x]];
    ufs[x]=ufs[ufs[x]];
}
int ufs_find(int x)
{
    if(ufs[x]==x) return x;
    ufs_internal_find(x);
    return mnsemi[x];
}
void calc_dominator_tree(int n)
{
    for(int i=0;i<n;++i)
        semi[i]=mnsemi[i]=ufs[i]=i;
    for(int x=n-1;x>0;x--)
    {
        int tfa=nodeID[fa[nodeName[x]]];
        for(auto &y:redge[nodeName[x]])
        if(vis[y])
        {
            int fy=ufs_find(nodeID[y]);
            if(semi[fy]<semi[x])
                semi[x]=semi[fy];
        }
        bucket[semi[x]].push_back(x);
        ufs_union(x,tfa);

        for(auto &y:bucket[tfa])
        {
            int fy=ufs_find(y);
            idom[nodeName[y]]=nodeName[semi[fy]<semi[y]?fy:tfa];
        }
        bucket[tfa].clear();
    }
    for(int x=1;x<n;++x)
        if(idom[nodeName[x]]!=nodeName[semi[x]])
            idom[nodeName[x]]=idom[idom[nodeName[x]]];
    idom[nodeName[0]]=-1;
}
void dfs(int x,int pre)
{
    num[x]=(x<n);
    for(auto &y:edge[x])
    if(y!=pre)
    {
        dfs(y,x);
        num[x]+=num[y];
    }
}
int main()
{
    memset(p,-1,sizeof(p));
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        --x;--y;
        add(x,y,c);
        add(y,x,c);
    }
    dijkstra();
    int tot=n;
    for(int j=0;j<e;++j)
    {
        if(dis[head[j]]==dis[head[j^1]]+w[j])
        {
            id[tot]=j/2;
            edge[head[j^1]].push_back(tot);
            edge[tot].push_back(head[j]);
            redge[head[j]].push_back(tot);
            redge[tot].push_back(head[j^1]);
            ++tot;
            //cout<<head[j^1]<<" "<<head[j]<<endl;
        }
    }

    memset(fa,-1,sizeof(fa));
    memset(idom,-1,sizeof(idom));
    memset(vis,0,sizeof(vis));
    ncnt=0;
    dfs(0);
    calc_dominator_tree(ncnt);
    for(int i=0;i<tot;++i)
        edge[i].clear();
    for(int i=1;i<tot;++i)
        edge[idom[i]].push_back(i);
    dfs(0,-1);
    for(int i=n;i<tot;++i)
        ans[id[i]]=num[i];
    for(int i=0;i<m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

 

Knapsack and Queries

来自Petrozavodsk Winter-2018. AtCoder Contest里的D题

题意是说,有Q次操作,分为两种,一是添加一个重量为w,价值为v的物品,保证插入的w单增,二是删除当前重量最小的物品。每次操作完之后,都有一个询问,询问能否从已有物品中选出一个子集,使得重量之和在模M之后在区间[l,r]内,并且价值和最大。

数据范围,。

Q和M一开始给定,之后每次操作强制在线。

做法:首先背包比较容易看出,但是有动态的插入、删除,这里的动态实际上是队列的模型,队尾入队,队首出队。我们将所有物品分成两部分,右半部分直接组成一个背包,左半部分记录从分界线开始的所有后缀组成的背包状态。那么插入就直接背进右边,删除直接删除左边第一个物品,不影响其他后缀,当左边为空时,就将右边所有物品移到左边,即将分界线移到最右侧,然后对每个后缀求背包。查询时,只需合并一次两边的背包,可以用单调队列优化。

这样每个物品最多只会用来做两次背包,做背包和合并两个背包的时间复杂度都是,所以总的时间复杂度为。因为要记录左侧每个后缀,所以空间复杂度最多也是。

 

代码仿照标程用了一些C++11的东西,比如template+using,swap两个vector,比较实用。

#include <bits/stdc++.h>
using namespace std;
class Crypto {
public:
    Crypto() {
        sm = cnt = 0;
        seed();
    }

    int decode(int z) {
        z ^= next();
        z ^= (next() << 8);
        z ^= (next() << 16);
        z ^= (next() << 22);
        return z;
    }

    void query(long long z) {
        const long long B = 425481007;
        const long long MD = 1000000007;
        cnt++;
        sm = ((sm * B % MD + z) % MD + MD) % MD;
        seed();
    }
private:
    long long sm;
    int cnt;

    uint8_t data[256];
    int I, J;

    void swap_data(int i, int j) {
        uint8_t tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    void seed() {
        uint8_t key[8];
        for (int i = 0; i < 4; i++) {
            key[i] = (sm >> (i * 8));
        }
        for (int i = 0; i < 4; i++) {
            key[i+4] = (cnt >> (i * 8));
        }

        for (int i = 0; i < 256; i++) {
            data[i] = i;
        }
        I = J = 0;

        int j = 0;
        for (int i = 0; i < 256; i++) {
            j = (j + data[i] + key[i%8]) % 256;
            swap_data(i, j);
        }
    }

    uint8_t next() {
        I = (I+1) % 256;
        J = (J + data[I]) % 256;
        swap_data(I, J);
        return data[(data[I] + data[J]) % 256];
    }
} c;

using Pair=pair<int,int>;
using LL=long long;
template<class T> using V = vector<T>;
const LL INF=(LL)1e18;

int mod,Q;
V<Pair> rq;
V<LL> now,las;
V<V<LL>> lq;
void init()
{
    now.resize(mod,0);
    las.resize(mod,0);
    lq.push_back(V<LL>(mod,0));
    for(int i=1;i<mod;++i) lq[0][i]=now[i]=las[i]=-INF;
}
int add(int x)
{
    return (x>=mod)?x-mod:x;
}
void packinit(V<LL> &a)
{
    a[0]=0;
    for(int i=1;i<mod;++i) a[i]=-INF;
}
void pack(V<LL> &a,const V<LL> &b,int w,int v)
{
    for(int i=0;i<mod;++i) a[i]=b[i];
    for(int i=0;i<mod;++i) a[add(i+w)]=max(a[add(i+w)],b[i]+v);
}
void push(int w,int v)
{
    rq.push_back(Pair(w,v));
    pack(las,now,w,v);
    swap(now,las);
}
void realloc()
{
    packinit(now);
    while(!rq.empty())
    {
        lq.push_back(V<LL>(mod));
        pack(lq.back(),lq[lq.size()-2],rq.back().first,rq.back().second);
        rq.pop_back();
    }
}
void pop()
{
    if(lq.size()==1) realloc();
    lq.pop_back();
}

LL ask(const V<LL> &a,const V<LL> &pb,int l,int r)
{
    static int que[1005];
    static LL b[1005];
    int head=0,tail=0,len=r-l+1;
    for(int i=0;i<mod;++i) b[i]=b[i+mod]=pb[i];
    LL ans=-INF;
    for(int i=mod-1,j=l;i>=0;--i)
    {
        while(head<tail && que[head]<l-i+mod) ++head;
        while(j<r-i+mod)
        {
            ++j;
            while(head<tail && b[que[tail-1]]<=b[j]) --tail;
            que[tail++]=j;
        }
        ans=max(ans,a[i]+b[que[head]]);
    }
    if(ans<0) ans=-1;
    return ans;
}
int main()
{
    scanf("%d%d",&mod,&Q);
    init();
    while(Q--)
    {
        int t,w,v,l,r;
        scanf("%d%d%d%d%d",&t,&w,&v,&l,&r);
        t=c.decode(t);
        w=c.decode(w);
        v=c.decode(v);
        l=c.decode(l);
        r=c.decode(r);
        if(t==1) push(w%mod,v);
        else pop();
        LL ans=ask(lq.back(),now,l,r);
        c.query(ans);
        printf("%lld\n",ans);
    }
    return 0;
}