• 13967708449
  • 1322284500@qq.com

Category Archive算法

分块小讲

博主在三天的奋战后,终于AC这些题目
博主在最近仔细研磨了港台立言的分块课件,收获颇丰,现在来写一写

首先分块是什么,分块是暴力

我们来看一个例子,假设我们要写区间加的题目(没错就是线段树),然后我们要用分块的方法打,对于线段树我们是在一些节点上面打标记,然后询问时下放标记就好了….分块也差不多,首先顾名思义,分块是把一个数组分成好多块,我们对于一个操作,对于包含整个块的,我们打一个tag,对于边上的我们直接暴力…..
如果一共有n个数,我们分成k个块,那么复杂度为O(\frac{n}{k}+k),然后当我们k\sqrt{n}时,复杂度就变成了\sqrt{n},然后对于m次操作,然后总复杂度就是m\sqrt{n}….
然后你就学会了一种会TLE的线段树暴力写法….
(当然分块不是用来写这些的,但是会这些,你已经会写数列分块前几题了)

数列分块入门1传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,单点查值。
1 \leq n \leq 50000,- 2^{31} \leq other,ans \leq 2^{31} - 1

分析:

我们来看第一题,哇,线段树,然后你过了……
好吧我们来看分块,直接分块,然后像我上面说的例子,打tag就好了

代码:

这里有一个小tip:
1. 最好预先处理所有数字在哪一个块
2. 块最好从0开始,这样子对于块x,他的起始位置和终止位置就是k\times x+1k\times x+k

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,k,a[N],tag[N],m;
int block[N],tot;
int main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++)
    {
        block[i]=tot;
        if(i%k==0) tot++; 
    }
    for(int i=1;i<=n;i++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r),read(c);
        if(opt==0)
        {
            int L=block[l],R=block[r];
            for(int j=L+1;j<R;j++) tag[j]+=c;
            if(block[l]==block[r]) for(int j=l;j<=r;j++) a[j]+=c;
            else 
            {
                for(int j=l;j<=block[l]*k+k;j++) a[j]+=c;
                for(int j=block[r]*k+1;j<=r;j++) a[j]+=c;
            }
        }
        else 
        {
            int R=r/k-(r%k==0?1:0);
            printf("%d\n",a[r]+tag[R]);
        }
    }
    return 0;
}

数列分块入门2传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,询问区间内小于某个值 x\times x 的元素个数。

分析:

这道题我们因为要算有多少个数字比询问的小,同时要维护加法,所以我们对于每一个块,维护一个单调递增的数列,对于一个块的加法,直接打tag因为,块内的所有数字都加上这个数字,他们的上升序列相对位置不边,对于两边的零散位置,直接暴力修改,改完直接重新排序就好了…
对于每一次询问,我们对于两边直接暴力\sqrt{n},对于块内的,二分位置….就好了….
博主在写这道题目的时候出了一点小意外,然后发现只分了一个块,然后每次询问都是暴力查询,复杂度变成n^2,然后松过了…..(一脸迷茫)

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; register LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,x[N],k;
int b[N],tot,tag[N];
int vec[N][250];
int siz[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]),vec[b[i]][++siz[b[i]]]=x[i];
    for(int i=0;i<=tot;i++) sort(vec[i]+1,vec[i]+siz[i]+1);
    for(int cas=1,opt,l,r,c;cas<=n;cas++)
    {
        read(opt);read(l),read(r),read(c);
        if(opt==0)
        {
            int L=b[l],R=b[r];
            for(register int i=L+1;i<R;i++) tag[i]+=c;
            if(b[l]==b[r]) 
            {   
                for(register int i=l;i<=r;i++) x[i]+=c;siz[L]=0;
                for(register int i=L*k+1;i<=min(L*k+k,n);i++) vec[L][++siz[L]]=x[i];
                sort(vec[L]+1,vec[L]+siz[L]+1);
            }
            else 
            {
                for(register int i=l;i<=L*k+k;i++) x[i]+=c;siz[L]=0;
                int h=min(L*k+k,n);
                for(register int i=L*k+1;i<=h;i++) vec[L][++siz[L]]=x[i];
                sort(vec[L]+1,vec[L]+siz[L]+1);
                for(register int i=R*k+1;i<=r;i++) x[i]+=c;siz[R]=0;
                h=min(R*k+k,n);
                for(register int i=R*k+1;i<=h;i++) vec[R][++siz[R]]=x[i];
                sort(vec[R]+1,vec[R]+siz[R]+1);
            }
        }
        else 
        {
            int L=b[l],R=b[r],ans=0;;
            if(L+2>=R)
            {
                for(register int i=l;i<=r;i++)
                    if(x[i]+tag[b[i]]<(LL)c*c)
                        ans++;
            }
            else
            {
                int h=(L+1)*k;
                for(register int i=l;i<=h;i++)
                    if(x[i]+tag[b[i]]<(LL)c*c)
                        ans++;
                if(R!=L)
                {
                    for(register int i=R*k+1;i<=r;i++)
                        if(x[i]+tag[b[i]]<(LL)c*c)
                            ans++;
                }
                for(register int i=L+1;i<=R-1;i++)
                {
                    register int ll=1,rr=siz[i],ret=0;
                    while(ll<=rr)
                    {
                        register int mid=(ll+rr)>>1;
                        if(vec[i][mid]+tag[i]>=(LL)c*c) rr=mid-1;
                        else ret=mid,ll=mid+1; 
                    }
                    ans+=ret;
                }
            }
            writeln(ans);
        }
    }
    return 0;
}

数列分块入门3传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,询问区间内小于某个值 x 的前驱(比其小的最大元素)。

分析:

这道题我感觉很假,我直接在上一题的代码上修改,把每次二分返回的位置,变成值,和ansmax就好了….

代码:



\#include<bits/stdc++.h> #define LL long long #define P pair<int,int> const LL N=1e5+10; const LL mod=1e9+7; const LL inf=1e17; using namespace std; template<typename tp> inline void read(tp &x) { x=0; char c=getchar(); bool f=0; for(;c<'0'||c>'9';f|=(c=='-'),c = getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar()); if(f) x=-x; } template<typename tp> inline void write(tp x) { if (x==0) return (void) (putchar('0')); if (x<0) putchar('-'),x=-x; LL pr[20]; register LL cnt=0; for (;x;x/=10) pr[++cnt]=x%10; while (cnt) putchar(pr[cnt--]+'0'); } template<typename tp> inline void writeln(tp x) { write(x); putchar('\n'); } int n,x[N],k; int b[N],tot,tag[N]; int vec[N][350]; int siz[N]; signed main() { read(n);k=sqrt(n); for(int i=1;i<=n;i++) {b[i]=tot;if(i%k==0&&i!=n) tot++;} for(int i=1;i<=n;i++) read(x[i]),vec[b[i]][++siz[b[i]]]=x[i]; for(int i=0;i<=tot;i++) sort(vec[i]+1,vec[i]+siz[i]+1); for(int cas=1,opt,l,r,c;cas<=n;cas++) { read(opt);read(l),read(r),read(c); if(opt==0) { int L=b[l],R=b[r]; for(register int i=L+1;i<R;i++) tag[i]+=c; if(b[l]==b[r]) { for(register int i=l;i<=r;i++) x[i]+=c;siz[L]=0; for(register int i=L*k+1;i<=min(L*k+k,n);i++) vec[L][++siz[L]]=x[i]; sort(vec[L]+1,vec[L]+siz[L]+1); } else { for(register int i=l;i<=L*k+k;i++) x[i]+=c;siz[L]=0; int h=min(L*k+k,n); for(register int i=L*k+1;i<=h;i++) vec[L][++siz[L]]=x[i]; sort(vec[L]+1,vec[L]+siz[L]+1); for(register int i=R*k+1;i<=r;i++) x[i]+=c;siz[R]=0; h=min(R*k+k,n); for(register int i=R*k+1;i<=h;i++) vec[R][++siz[R]]=x[i]; sort(vec[R]+1,vec[R]+siz[R]+1); } } else { int L=b[l],R=b[r],ans=-1; if(L+2>R) { for(register int i=l;i<=r;i++) if(x[i]+tag[b[i]]<c) ans=max(ans,x[i]+tag[b[i]]); } else { int h=(L+1)*k; for(register int i=l;i<=h;i++) if(x[i]+tag[b[i]]<c) ans=max(ans,x[i]+tag[b[i]]); if(R!=L) { for(register int i=R*k+1;i<=r;i++) if(x[i]+tag[b[i]]<c) ans=max(ans,x[i]+tag[b[i]]); } for(register int i=L+1;i<=R-1;i++) { register int ll=1,rr=siz[i],ret=0; while(ll<=rr) { register int mid=(ll+rr)>>1; if(vec[i][mid]+tag[i]>=c) rr=mid-1; else ret=mid,ll=mid+1; } if(ret) ans=max(ans,vec[i][ret]+tag[i]); } } writeln(ans); } } return 0; }

数列分块入门4传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,区间求和。

分析:

然后这道题目,非常简单啊!只要对于每一个块多维护一个sum就好了,水一水就过了….

代码:

#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; register LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,x[N],k;
int b[N],tot,tag[N];
int vec[N],siz[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;siz[tot]++;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]),vec[b[i]]+=x[i];
    for(int cas=1,opt,l,r,c;cas<=n;cas++)
    {
        read(opt);read(l),read(r),read(c);
        if(opt==0)
        {
            int L=b[l],R=b[r];
            for(register int i=L+1;i<R;i++) tag[i]+=c;
            if(b[l]==b[r]) 
            {
                vec[b[l]]=0;
                for(register int i=l;i<=r;i++) x[i]+=c;
                for(int i=b[l]*k+1;i<=b[l]*k+k;i++)
                    vec[b[l]]+=x[i];
            }
            else 
            {
                vec[b[l]]=0;
                for(register int i=l;i<=L*k+k;i++) x[i]+=c;
                for(int i=b[l]*k+1;i<=b[l]*k+k;i++)
                    vec[b[l]]+=x[i];
                vec[b[r]]=0;
                for(register int i=R*k+1;i<=r;i++) x[i]+=c;
                for(int i=b[r]*k+1;i<=b[r]*k+k;i++)
                    vec[b[r]]+=x[i];
            }
        }
        else 
        {
            int L=b[l],R=b[r],ans=0;
            if(L+2>R)
            {
                for(register int i=l;i<=r;i++)
                    ans+=x[i]+tag[b[i]];
            }
            else
            {
                int h=(L+1)*k;
                for(register int i=l;i<=h;i++)
                    ans+=x[i]+tag[b[i]];
                if(R!=L)
                {
                    for(register int i=R*k+1;i<=r;i++)
                        ans+=x[i]+tag[b[i]];
                }
                for(register int i=L+1;i<=R-1;i++)
                    ans+=vec[i]+tag[i]*siz[i];
            }
            writeln(ans%(c+1));
        }
    }
    return 0;
}

数列分块入门5传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间开方,区间求和。

分析:

妈的,区间开方怎么写,博主刚刚看到这道题目的时候,想打人,这个东西完全不会啊,求和怎么写啊…..
然后弃疗…..
然后想了想,我们可以发现一个数字凯放最多20次(可能没有那么多),那么这么多次以后,数字就变成一了,然后我就对每一个块维护了一个数字不唯一的vector,每次对于块打tag,然后询问时一起开方,这样子复杂度是O(n\sqrt{n}+20\times n)的,过了….

代码:

#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int b[N],siz[N],tot,tag[N],sum[N];
deque<int> vec[N];
void Sqrt(int &a,int b){while(b&&a>1) b--,a=sqrt(a);}
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;siz[tot]++;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) {read(x[i]),sum[b[i]]+=x[i]; if(x[i]>1) vec[b[i]].push_back(i);}
    for(int cas=1;cas<=n;cas++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r),read(c);
        if(opt==0)
        {
            int L=b[l],R=b[r];
            for(int i=L+1;i<R;i++) tag[i]+=1;
            if(b[l]==b[r]) 
            {   
                for(int i=l;i<=r;i++) x[i]=sqrt(x[i]);
                vec[L].clear();sum[L]=0;
                for(int i=L*k+1;i<=min(L*k+k,n);i++) 
                {
                    sum[L]+=x[i];
                    if(x[i]>1) vec[L].push_back(i);
                }
            }
            else 
            {
                for(int i=l;i<=L*k+k;i++) x[i]=sqrt(x[i]);
                vec[L].clear();sum[L]=0;
                for(int i=L*k+1;i<=min(L*k+k,n);i++) 
                {
                    sum[L]+=x[i];
                    if(x[i]>1) vec[L].push_back(i);
                }
                for(int i=R*k+1;i<=r;i++) x[i]=sqrt(x[i]);
                vec[R].clear();sum[R]=0;
                for(int i=R*k+1;i<=min(R*k+k,n);i++) 
                {
                    sum[R]+=x[i];
                    if(x[i]>1) vec[R].push_back(i);
                }
            }
        }
        else 
        {
            int L=b[l],R=b[r],ans=0;;
            if(L+2>=R)
            {
                for(int i=L*k+1;i<=min(n,R*k+k);i++) Sqrt(x[i],tag[b[i]]);
                for(int i=l;i<=r;i++) ans+=x[i];
                for(int i=L;i<=R;i++)
                {
                    vec[i].clear();sum[i]=0;tag[i]=0;
                    for(int j=i*k+1;j<=min(i*k+k,n);j++) {sum[i]+=x[j];if(x[j]>1) vec[i].push_back(j);}
                }
            }
            else
            {
                if(tag[L])
                {
                    deque<int> de;
                    while(!vec[L].empty())
                    {
                        int now=vec[L].front();vec[L].pop_front();
                        sum[L]-=x[now];Sqrt(x[now],tag[L]);
                        sum[L]+=x[now];
                        if(x[now]>1) de.push_back(now);
                    }tag[L]=0;
                    while(!de.empty()) vec[L].push_back(de.front()),de.pop_front();
                }
                for(int i=l;i<=L*k+k;i++) ans+=x[i];
                if(tag[R])
                {
                    deque<int> de;
                    while(!vec[R].empty())
                    {
                        int now=vec[R].front();vec[R].pop_front();
                        sum[R]-=x[now];Sqrt(x[now],tag[R]);
                        sum[R]+=x[now];
                        if(x[now]>1) de.push_back(now);
                    }tag[R]=0;
                    while(!de.empty()) vec[R].push_back(de.front()),de.pop_front();
                }
                for(int i=R*k+1;i<=r;i++) ans+=x[i];
                for(int i=L+1;i<=R-1;i++)
                {
                    if(tag[i])
                    {
                        deque<int> de;
                        while(!vec[i].empty())
                        {
                            int now=vec[i].front();vec[i].pop_front();
                            sum[i]-=x[now];Sqrt(x[now],tag[i]);
                            sum[i]+=x[now];
                            if(x[now]>1) de.push_back(now);
                        }
                        while(!de.empty()) vec[i].push_back(de.front()),de.pop_front();
                        tag[i]=0;
                    }
                    ans+=sum[i];
                }
            }
            writeln(ans);
        }
    }
    return 0;
}

(哎呀呀好像代码格式崩了,嘤嘤嘤)

数列分块入门6传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及单点插入,单点询问,数据随机生成。

分析:

诶,我靠,这他妈怎么还单点插入的啊,要死啊,博主刚看题时的心里想法…..
我们知道数列分块在分完块以后,然后对于一个块,我们已经确定了他的大部分信息,插入点是插不进去了(大佬算了,你们爱怎么写怎么写),那么什么东西可以做到单点插入呢…没错是链表….
然后,我们对于一个链,记录他的头和大小,每次询问和,插入先跳到对应的链再跳到对应的点,进行O(1)插入和询问….这是有一个要点,对于一个链如果他大于2\times k时,我们要进行重建以保证复杂度….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N],cnt;
struct Node{int next,cost;}node[N*2],top[N];
int siz[N],tot;
signed main()
{
    read(n);k=sqrt(n);cnt=n;
    for(int i=1;i<=n;i++) 
    {   
        siz[tot]++;
        if(i%k==1) top[tot].cost=i,top[tot].next=tot+1;
        if(i%k==0&&i!=n) tot++;
    }
    top[tot].next=0;
    for(int i=1;i<=n;i++) read(x[i]),node[i].cost=x[i];
    for(int i=1;i<=n;i++) if(i%k!=0&&i!=n) node[i].next=i+1;
    for(int cas=1;cas<=n;cas++)
    {
        int opt,l,r,c,flag=0,now=0,sum=0,zz;
        read(opt),read(l),read(r),read(c);
        if(opt==0)
        {
            while(sum+siz[now]<l) sum+=siz[now],now=top[now].next; zz=now;
            now=top[now].cost;
            if(l-sum==1) flag=1;
            while(l-sum-2>0) l--,now=node[now].next;
            if(flag)
            {
                node[++cnt].cost=r;
                node[cnt].next=now;
                top[zz].cost=cnt;
                siz[zz]++;
            }
            else
            {
                node[++cnt].cost=r;
                node[cnt].next=node[now].next;
                node[now].next=cnt;
                siz[zz]++;
            }
            if(siz[zz]==2*k)
            {
                now=top[zz].cost;
                int tiao=siz[zz];
                while(tiao>k+1) tiao--,now=node[now].next;
                top[++tot].next=top[zz].next;
                top[zz].next=tot;
                top[tot].cost=node[now].next;
                node[now].next=0;
                siz[zz]=siz[zz]-k;
                siz[tot]=k;
            }
        }
        else 
        {
            while(sum+siz[now]<r) sum+=siz[now],now=top[now].next; zz=now;
            now=top[now].cost;
            while(r-sum-1>0) r--,now=node[now].next;
            printf("%d\n",node[now].cost);
        }
    }
    return 0;
}

数列分块入门7传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间乘法,区间加法,单点询问。

分析:

对于这个题目,我们可以分类讨论,打两个tag,一个表示乘法,一个表示加法,最终答案为x[i]\times time[block[i]] + tag[block[i]],所以对于一次加法,对于一个块我们直接加到tag上门,然后对于零散的,要先下放整个块的乘法标记,在暴力加….对于一次乘法,我们对于两个tag,直接乘上这个值就好了,零散的也是要先下放….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=1e4+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int b[N],siz[N],tot,tag[N],times[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=0;i<=tot;i++) times[i]=1;
    for(int i=1;i<=n;i++) read(x[i]),x[i]%=mod;
    for(int cas=1;cas<=n;cas++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r),read(c);c%=mod;
        int L=b[l],R=b[r];
        if(opt==0)
        {
            for(int i=L+1;i<=R-1;i++) (tag[i]+=c)%=mod;
            for(int i=k*L+1;i<=k*L+k;i++) 
            {
                (x[i]=x[i]*times[L])%=mod;
                if(i>=l&&i<=r) (x[i]+=c)%=mod;
            }
            times[L]=1;
            if(R!=L) 
            {
                for(int i=R*k+1;i<=R*k+k;i++)
                {
                    (x[i]=x[i]*times[R])%=mod;
                    if(i>=l&&i<=r) (x[i]+=c)%=mod;
                }
                times[R]=1;
            }
        }
        else if(opt==1)
        {
            for(int i=L+1;i<=R-1;i++) (times[i]*=c)%=mod,(tag[i]*=c)%=mod;
            for(int i=k*L+1;i<=k*L+k;i++) 
            {
                (x[i]=x[i]*times[L]+tag[L])%=mod;
                if(i>=l&&i<=r) (x[i]*=c)%=mod;
            }
            times[L]=1;tag[L]=0;
            if(R!=L) 
            {
                for(int i=R*k+1;i<=R*k+k;i++)
                {
                    (x[i]=x[i]*times[R]+tag[R])%=mod;
                    if(i>=l&&i<=r) (x[i]*=c)%=mod;
                }
                times[R]=1;tag[R]=0;
            }
        }
        else printf("%d\n",(x[r]*times[b[r]]+tag[b[r]])%mod);
    }
    return 0;
}

数列分块入门8传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间询问等于一个数 c 的元素,并将这个区间的所有元素改为 c

分析:

这道题目,我还是有一个tag,tag0时,块内的数就是当前值,反之就是tag上门的值….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=1e4+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int b[N],tot,tag[N],siz[N];
map<int,int> Map[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;siz[tot]++;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]),Map[b[i]][x[i]]++;
    for(int cas=1;cas<=n;cas++)
    {
        int l,r,c,ans=0;
        read(l),read(r),read(c);
        int L=b[l],R=b[r];
        if(L+2>=R)
            for(int i=l;i<=r;i++) 
            {
                if(tag[b[i]]==c) ans++;
                else if(!tag[b[i]]) ans+=(x[i]==c);
            }
        else 
        {
            for(int i=L+1;i<=R-1;i++) if(!tag[i]) ans+=Map[i][c]; else ans+=(tag[i]==c)*siz[i];
            for(int i=l;i<=min(r,L*k+k);i++) if(!tag[L]) ans+=(x[i]==c); else ans+=(tag[L]==c);
            if(R!=L) for(int i=R*k+1;i<=r;i++) if(!tag[R]) ans+=(x[i]==c); else ans+=(tag[R]==c);
        }
        printf("%d\n",ans);
        for(int i=L+1;i<=R-1;i++) tag[i]=c;
        Map[L].clear();
        for(int i=L*k+1;i<=L*k+k;i++)
        {
            if(tag[L]) x[i]=tag[L]; if(i>=l&&i<=r) x[i]=c;
            Map[L][x[i]]++;
        }tag[L]=0;
        if(R!=L)
        {
            Map[R].clear();
            for(int i=R*k+1;i<=R*k+k;i++)
            {
                if(tag[R]) x[i]=tag[R]; if(i>=l&&i<=r) x[i]=c;
                Map[R][x[i]]++;
            }
            tag[R]=0;
        }
    }
    return 0;
}

数列分块入门9传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及询问区间的最小众数。

分析:

哇,莫队,哇不会!!!!!!
怎么办啊,好吧我们分块算了,分块复杂度一样,还tm是在线的,分块牛逼
这个东西,我们要先tm的哈希,因为这些数字太大了,然后我维护了zhong[i][j]表示i块到j块的最小众数,vec[i]表示i块的数字集合,num[i][j]表示到第i个块的j数字个数的前缀和…
然后对于一次询问,我们已经知道中间块的众数,然后依次加入两边的零散部分去更新答案就好了…

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=1e4+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int block[N],tot,ha,to[N];
map<int,int> Hash;
int num[400][N],flag[N];
P zhong[400][400];
vector<int> vec[400];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {block[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) {read(x[i]);Hash[x[i]]=1;}
    for(auto v:Hash)  Hash[v.first]=++ha,to[ha]=v.first;
    for(int i=1;i<=n;i++) x[i]=Hash[x[i]];
    for(int i=0;i<=tot;i++)
    {
        zhong[i][i].second=0;
        for(int j=i*k+1;j<=min(k*i+k,n);j++) flag[x[j]]++;
        for(int j=1;j<=ha;j++)  
        {
            if(flag[j]>zhong[i][i].second) zhong[i][i].first=j,zhong[i][i].second=flag[j];
            if(flag[j]>0) vec[i].push_back(j);
            num[i][j]=num[i-1][j]+flag[j],flag[j]=0;
        }
    }
    for(int i=0;i<=tot;i++)
        for(int j=i+1;j<=tot;j++)
        {
            zhong[i][j]=zhong[i][j-1];
            int siz=vec[j].size();
            for(int kk=0;kk<siz;kk++)
            {
                int x=vec[j][kk],y=num[j][x]-num[i-1][x];
                if(zhong[i][j].second<y||(zhong[i][j].second==y&&zhong[i][j].first>x)) 
                    zhong[i][j].first=x,zhong[i][j].second=y;
            }
        }
    for(int i=1;i<=n;i++) 
    {
        int l,r;
        read(l),read(r);
        int L=block[l],R=block[r];
        if(L+2>=R)
        {
            P ans;ans.second=0;
            for(int i=l;i<=r;i++)
            {
                flag[x[i]]++;
                if(flag[x[i]]>ans.second||(ans.second==flag[x[i]]&&ans.first>x[i]))
                    ans.first=x[i],ans.second=flag[x[i]];
            }
            for(int i=l;i<=r;i++) flag[x[i]]--;
            printf("%d\n",to[ans.first]);
        }
        else
        {
            P ans=zhong[L+1][R-1];
            for(int i=l;i<=L*k+k;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]];
                flag[x[i]]++;
                if(flag[x[i]]>ans.second||(ans.second==flag[x[i]]&&ans.first>x[i]))
                    ans.first=x[i],ans.second=flag[x[i]];
            }
            for(int i=k*R+1;i<=r;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]];
                flag[x[i]]++;
                if(flag[x[i]]>ans.second||(ans.second==flag[x[i]]&&ans.first>x[i]))
                    ans.first=x[i],ans.second=flag[x[i]];
            }
            for(int i=l;i<=L*k+k;i++) flag[x[i]]=0;
            for(int i=k*R+1;i<=r;i++) flag[x[i]]=0;
            printf("%d\n",to[ans.first]);
        }
    }
    return 0;
}

[2009国家集训队]小Z的袜子(hose)传送门

###Description
作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1N编号,然后从编号LR(尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数NMN为袜子的数量,M为小Z所提的询问的数量。接下来一行包含N个正整数C_i,其中C_i表示第i只袜子的颜色,相同的颜色用相同的数字表示。再接下来M行,每行两个正整数LR表示一个询问。

Output

包含M行,对于每个询问在一行中输出分数\frac{A}{B}表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出\frac{0}{1},否则输出的\frac{A}{B}必须为最简分数。(详见样例)

分析:

这道题和上门那个众数的题目很想,也是要维护前缀和,就是维护答案的地方有一些小技巧,如果中间块的答案已知,现在枚举两边的零散部分,x_i,这个值在块中出现过,那么我们求出块中出现的次数num,答案先减去\frac{num\times (num-1)}{2},最后统计完了一起加上就好了….

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=1e4+7;
const LL inf=0x3f3f3f3f;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,k;
int x[N],block[N],tot;
int num[250][N],flag[N];
LL anss[250][250],vis[N];
signed main()
{
    read(n),read(m);k=sqrt(n);
    for(int i=1;i<=n;i++){block[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]);
    for(int i=0;i<=tot;i++)
    {
        for(int j=i*k+1;j<=min(n,i*k+k);j++) flag[x[j]]++;
        for(int j=0;j<=n;j++) 
        {
            if(flag[j]) anss[i][i]+=flag[j]*(flag[j]-1)/2;
            num[i][j]=(i-1>=0?num[i-1][j]+flag[j]:flag[j]);
        }
        for(int j=i*k+1;j<=min(n,i*k+k);j++) flag[x[j]]--;
    }
    for(int i=0;i<=tot;i++)
    {
        for(int j=i+1;j<=tot;j++)
        {
            anss[i][j]=anss[i][j-1];
            for(int l=k*j+1;l<=min(n,k*j+k);l++)
                if(!vis[x[l]])
                {
                    vis[x[l]]=1;
                    int zz=num[j-1][x[l]]-(i-1>-1?num[i-1][x[l]]:0);
                    int mdzz=num[j][x[l]]-(i-1>-1?num[i-1][x[l]]:0);
                    anss[i][j]+=mdzz*(mdzz-1)/2-zz*(zz-1)/2;
                }
            for(int l=k*j+1;l<=min(n,k*j+k);l++) vis[x[l]]=0;
        }
    }
    memset(flag,0,sizeof(flag));
    for(int cas=1;cas<=m;cas++)
    {
        int l,r,ans=0;
        read(l),read(r);
        int L=block[l],R=block[r];
        if(L+2>=R)
        {
            for(int i=l;i<=r;i++) flag[x[i]]++;
            for(int i=l;i<=r;i++) if(!vis[x[i]]){vis[x[i]]=1;ans+=flag[x[i]]*(flag[x[i]]-1)/2;}
            for(int i=l;i<=r;i++) vis[x[i]]=0,flag[x[i]]--;
        }
        else 
        {
            ans=anss[L+1][R-1];
            for(int i=l;i<=L*k+k;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]],
                    ans-=flag[x[i]]*(flag[x[i]]-1)/2;
                flag[x[i]]++;
            }
            for(int i=R*k+1;i<=r;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]],ans-=flag[x[i]]*(flag[x[i]]-1)/2;
                flag[x[i]]++;
            }
            for(int i=l;i<=L*k+k;i++) if(!vis[x[i]]){vis[x[i]]=1;ans+=flag[x[i]]*(flag[x[i]]-1)/2;}
            for(int i=R*k+1;i<=r;i++) if(!vis[x[i]]){vis[x[i]]=1;ans+=flag[x[i]]*(flag[x[i]]-1)/2;}
            for(int i=l;i<=L*k+k;i++) vis[x[i]]=flag[x[i]]=0;
            for(int i=R*k+1;i<=r;i++) vis[x[i]]=flag[x[i]]=0;
        }
        if(ans==0) printf("0/1\n");
        else 
        {
            int zz=r-l+1; zz=zz*(zz-1)/2;
            int mdzz=__gcd(ans,zz);
            printf("%lld/%lld\n",ans/mdzz,zz/mdzz);
        }
    }
    return 0;
}

最后%%%hzwer大佬…然后讲完了,欢迎提问!!!

自己都不会的联通小讲

前言:

近日回顾去年各位大佬的课件,发现什么都不会…(靠,大佬去年比我今年还强)然后对着现充fyy的课件一看一下午,终于搞懂一点有关联通分量的有关东西

前置知识:(拷自fyy课件)

  1. 强连通分量(SCC):
    >在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。
  2. ….

其他什么的知识点就不讲了直接开始求实际的东西,要用到的我看着说.然后kosaraju算法我也不说了,没有tarjan强,也没有他好用…(%%%tarjan老爷爷)

有向图求强连通分量

对于图G的每个点,记录下每个点的dfs序(dfn)和以它为根的搜索树中所能到达节点的dfn的最小值(low).
对于一个点u,它指向的点v分为三种情况.
1. v已经被访问过,且是它的祖先\tolow[u]=min(low[u],dfn[v])
2. v已经被访问过,不是它的祖先\to不在同一个强连通分量中,跳过
3. v尚未被访问过,向下dfs,low[u]=min(low[u],dfn[v]).

当点u的dfn=low,意味着以这个点为根的子树中不存在可以指向u的祖先。那么u到可以到达u的最深的孩子构成一个强连通分量。用一个栈O(V)维护这些信息。
复杂度显然也是O(V+E)….
(这种东西看分析是看不懂的直接看代码,磨一磨就好了)

代码:

void dfs(int now)//now是当前点
{
    vis[now]=1;st.push(now);//st是栈
    dfn[now]=low[now]=++num;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to]) dfs(to),low[now]=min(low[now],low[to]);
        else if(!scc[to]) low[now]=min(low[now],dfn[to]);
    }
    if(dfn[now]==low[now])
    {
        sccn++;//scc存的是每个点所在的强联通分量,sccn存数目
        while(true)
        {
            int fron=st.top();st.pop();
            cost[sccn]+=xx[fron];
            scc[fron]=sccn;
            if(fron==now) break;
        }
    }
}

无向图的割顶和桥:

给定一张无向图G=(V,E)。如果删除某个点u后,连通分量的数目增加,则称uG的割顶(cut vertex);如果删除某条边(u,v)后,连通分量的数目增加,则称(u,v)G的桥(bridge)。删除一个连通图中的割顶或桥,会使图不连通。

怎么求呢?
从一个节点开始做dfs,会形成一颗搜索树。与有向图中的搜索树不同。无向图中搜索树中各个子树之间不存在任何连边。
对于每次dfs的根节点,如果它有大于一个孩子,它一定是割顶。
对于其他每个节点u记录下它的dfn_ulow_u。如果点u存在一个孩子点v满足low[v]\geqslant dfn[u],即点v不能到达点u以上的祖先,把点u删去会使图的连通分量增加,从而点u是一个割顶。
对于一条边e_1=(u,v)如果uv的祖先,且low[v]>dfn[u],在没有重边e_2=(u,v)的情况下,e_1即是一座桥。

代码:

GD\to割点
GB\to割边

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=998244353;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,ans;
int head[N],cnt;
int vis[N],dfn[N],low[N],num;
struct Edge{int next,to;}edge[N*5];
inline void add(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
int GD[N],num_GD;
vector<P> GB; 
void dfs(int now,int fa)
{
    vis[now]=1;
    dfn[now]=low[now]=++num; int son=0;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;if(to==fa) continue;
        if(!vis[to]) 
        {
            dfs(to,now);
            low[now]=min(low[now],low[to]);
            if(low[to]>=dfn[now]) son++;
        }
        else low[now]=min(low[now],dfn[to]);
    }
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;if(to==fa) continue;
        if(low[to]>dfn[now]) 
            GB.push_back(P(min(to,now),max(to,now)));
    }
    if(son>=2||(son==1&&fa)) GD[++num_GD]=now;
}
void tarjan() {for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);}
signed main()
{
    read(n),read(m);
    for(int i=1,u,v;i<=m;i++) read(u),read(v),add(u,v),add(v,u);
    tarjan();
    sort(GD+1,GD+num_GD+1);
    for(int i=1;i<=num_GD;i++) printf("%d ",GD[i]); 
    if(num_GD==0) puts("Null"); else puts("");
    sort(GB.begin(),GB.end());
    int siz=GB.size();
    for(int i=0;i<siz;i++) printf("%d %d\n",GB[i].first,GB[i].second);
    return 0;
}

双联通分量:

给定一张无向连通图G=(V,E)。
如果删除任意点u后,图仍旧连通(或任意两点存在两条“点不重复”的路径),则称G是点-双连通的(一般简称双连通,biconnected);
如果删除某条边(u,v)后,图仍旧连通(或任意两点存在两条“边不重复”的路径),则称G是边-双连通的(edge-biconnected)。
G的极大点-双连通子图称为(点)双连通分量(Biconnected Component,BCC),或块(block)。
G的极大边-双连通子图称为边-双连通分量(edge-biconnected component)

无向图求点双:

桥不属于任何边-双联通分量,其他每条边恰好属于一个边-双连通分量。
删除所有的桥后,每个联通分量对应原图中的一个边-双联通分量。
将所有的边-双联通分量缩点后,得到的是一棵树。

边-双联通分量的求解非常简单。
先对G求出它所有的桥。断开所有的桥,求出它的所有连通分量。每个联通分量就是原图的一个双联通分量。

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=998244353;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,anss;
int head[N],cnt=1;
int vis[N],dfn[N],low[N],num;
int cant[N*5],ans[N];
struct Edge{int next,to;}edge[N*5];
inline void add(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
void dfs(int now,int fa)
{
    vis[now]=1;
    dfn[now]=low[now]=++num;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to; if(to==fa) continue;
        if(!vis[to]) dfs(to,now),low[now]=min(low[now],low[to]);
        else low[now]=min(low[now],dfn[to]);
    }
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to; if(to==fa) continue;
        if(low[to]>dfn[now]) cant[i]=cant[i^1]=1;
    }
}
void tarjan(){for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,i);}
void dfs_ans(int now,int zu)
{
    ans[now]=zu;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(ans[to]||cant[i]) continue;
        dfs_ans(to,zu);
    }
}
int main()
{
    read(n),read(m);
    for(int i=1,u,v;i<=m;i++) read(u),read(v),add(u,v),add(v,u);
    tarjan();
    for(int i=1;i<=n;i++) if(!ans[i]) anss++,dfs_ans(i,i);
    printf("%d\n",anss);
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");
    return 0;
}

无向图点双:

在割顶算法的基础上稍作改动就可以求解点-双连通分量.
和强连通算法一样维护一个栈。但由于割顶可以属于多个点-双连通分量,我们将边压入栈。
当存在low[v]>=dfn[u]即产生割顶时,我们将栈中的边取出,与这些边有关的点位于同一个点-双连通分量。
最好用vector记录一下每个点-双连通分量有哪些点,因为割顶记录的所处哪个连通分量的信息没有任何意义。


int vis[N], dfn[N], low[N], num; stack<Edge> st; int scc[N], sccn, new_sccn; void dfs(int now, int fa) { vis[now] = 1; dfn[now] = low[now] = ++num; for (int i = head[now]; i; i = edge[i].next) { int to = edge[i].to; if (!dfn[to]) { st.push(Edge{now, to}); dfs(to, now); low[now] = min(low[now], low[to]); if (low[to] >= dfn[now]) { node[++sccn].l = inf; vector<P> zz;zz.clear(); while (1) { Edge fron = st.top(); st.pop(); if (scc[fron.next] != sccn) { zz.push_back(P(fron.next,scc[fron.next])); scc[fron.next] = sccn; node[sccn].l = min(node[sccn].l, fron.next); node[sccn].r = max(node[sccn].r, fron.next); } if (scc[fron.to] != sccn) { zz.push_back(P(fron.to,scc[fron.to])); scc[fron.to] = sccn; node[sccn].l = min(node[sccn].l, fron.to); node[sccn].r = max(node[sccn].r, fron.to); } if (fron.next == now && fron.to == to) break; } if(zz.size()<=2) { node[sccn].l=inf,node[sccn].r=0,sccn--; int siz=zz.size(); for(int i=0;i<siz;i++) scc[zz[i].first]=zz[i].second; } } } else if (dfn[to] < dfn[now] && to != fa) { st.push(Edge{now, to}); low[now] = min(low[now], dfn[to]); } } } void tarjan() { for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i, 0); }

参考:fyy神仙的课件…..

凸包小讲

今天,心血来潮,花了一个下午时间学习了凸包,本来对着教程(文字)写代码,后来实在调不出来,只能对着别人的手模了。(太菜了)

我们先来看一道模板题:题目地址

题意:给出n个点,然后问你凸包(能包括所有点的一个图)的周长。。。

一道凸包经典题目。。。那么我们直接来讲凸包。。。

我学习了一种最为常见的算法:Graham扫描法

大概思想是先找到凸包上的一个点,然后从那个点开始按逆时针方向逐个找凸包上的点。。。我们已经知道如果已知凸包上的一个点,那么我们去找和他相邻的最外圈的点加入凸包。。。

所以我们如何找呢。。。这里就用到了二维叉积,已知两个向量 a 和 b,a×(叉)b就等于 (xa*yb)-(ya*xb)。。。如果其小于0,就表示a在b的逆时针方向。。。既然这样那我们就可以用叉积来求向量的位置关系。。。

步骤如下:

  1. 我们先在输入时找到y最小的那个点node[0],易得它一定在凸包里。。。
  2. 我们将所有的点(除了找出来的那个)按照幅角进行排序,方法就是利用叉积,我们比较两个点,从node[0]出发到这两个点变成两个向量。。。然后叉积判断位置。。。排完序以后,点都绕着node[0]按照逆时针排列。。。
  3. 我们O(n)枚举每一个点,看栈顶的元素和当前点与栈顶-1的元素构成的图是不是最优的,利用叉积,如果栈顶的元素在其逆时针,我们就将其pop出队列,直到符合条件,我们就直接把当前点加入队尾。。。

如下图:

20150530145453912

然后代码如下:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
namespace Graham
{
    int n;
    struct Node{double x,y;int name;}node[N];
    vector v;
    void read_node()
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&node[i].x,&node[i].y);
            if(node[i].y<node[0].y)
                swap(node[i].x,node[0].x),swap(node[i].y,node[0].y);
        }
        n--;
    }
    double Cross_product(Node a,Node b,Node c){return (b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y);}
    bool cmp(Node a,Node b)
    {
        double angle=(a.x-node[0].x)*(b.y-node[0].y)-(b.x-node[0].x)*(a.y-node[0].y);
        if(angle==0)return abs(a.x-node[0].x)<abs(b.x-node[0].x); 
        if(angle<0)return false;
        return true;
    }
    double solve()
    {
        double ans=0;v.push_back(node[0]);
        sort(node+1,node+n+1,cmp);
        for(int i=1;i1&&Cross_product(v[v.size()-2],v[v.size()-1],node[i])<=0) 
                v.pop_back();
            v.push_back(node[i]);
        }
        v.push_back(node[0]);
        for(int i=0;i<v.size()-1;i++)
            ans+=sqrt(pow(abs(v[i].x-v[i+1].x),2)+pow(abs(v[i].y-v[i+1].y),2));
        return ans;
    }
}
using namespace Graham;
main()
{
    read(n);
    read_node();
    printf("%.2lf",solve());
    return 0;
}

Kruskal重构树

 

刚刚学了Kruskal重构树,然后打了一个模板,现在趁热打一个博客。。。

我们来看一道裸体:

火狐截图_2018-07-24T12-11-20.140Z

这道题看起来好像很水,我们可以跑最小生成树然后套一个倍增LCA,统计路径上的最大值。。。但我们现在用一个更加奇妙的方法来做。。。叫做Kruskal重构树。。。

我们思考一下我们做Kruskal的过程,就是从小到大加边,那么我们可知加入的边是递增的,那么一条连上的最大边值,一定是后加入的,那我们只要创造一种结构,后加入的边在结构的上面,每次直接LCA就求出答案。。。没错就是它。。。

我们思考加入边时,我们建立一个虚拟节点,把两个节点连到虚拟节点上。。。

然后当我们合并两棵树时,我们直接把虚拟节点连到新建的虚拟节点上就好了。。。最后我们发现所有原树上的节点都是树的底层叶子,他们没有儿子。。。

这棵建好的树有很多好的性质,所有虚拟节点的权值都小于其父亲,而且这是一颗二叉树。。。

那么我们询问两个点之间的最大边值时,直接跳LCA,输出其节点的值就ok了。。。

 直接上代码吧:

#include<bits/stdc+.h>
#define LL long long
using namespace std;
const LL N=15e3+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO 
{
    template inline void read(tp &x) 
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x) 
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x) 
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n,m,fa[N*2],cnt,k;
int fath[N*2][22],dep[N*2];
int val[N*2],ch[N*2][2];
struct Undirected_graph{int from,to,cost;}figure[N*2];
bool cmp(Undirected_graph a,Undirected_graph b){return a.cost<b.cost;}
int get_fa(int now)
{
    if(fa[now]==now)return now;
    return fa[now]=get_fa(fa[now]);
}
//----------------核心代码------------------
void build()
{
    int flag=0;
    for(int i=1;i<=m;i++)
    {
        int from=figure[i].from,to=figure[i].to,cost=figure[i].cost;
        if(flag==n-1)break;
        if(get_fa(from)==get_fa(to))continue;
        val[++cnt]=cost;
        ch[cnt][0]=fa[from],ch[cnt][1]=fa[to];
        fath[fa[from]][0]=fath[fa[to]][0]=cnt;
        fa[fa[from]]=fa[fa[to]]=cnt;flag++;
    }
}
//---------------核心代码---------------------
void dfs(int now)
{
    if(now==0)return;
    for(int i=1;i<=20;i++)
        fath[now][i]=fath[fath[now][i-1]][i-1];
    dep[ch[now][0]]=dep[ch[now][1]]=1+dep[now]+1;
    dfs(ch[now][0]),dfs(ch[now][1]);
}
int lca(int l,int r)
{
    if(dep[l]=0;i--)
        if(dep[fath[l][i]]>=dep[r])
            l=fath[l][i];
    if(l==r) return val[l];
    for(int i=20;i>=0;i--)
        if(fath[l][i]!=fath[r][i])
            l=fath[l][i],r=fath[r][i];
    return val[fath[l][0]];
}
main() 
{
    read(n),read(m),read(k);cnt=n;
    for(int i=1;i<=m;i++)
        read(figure[i].from),read(figure[i].to),read(figure[i].cost);
    sort(figure+1,figure+m+1,cmp);
    for(int i=1;i<=n*2;i++) fa[i]=i,fath[i][0]=i;
    build();dep[cnt]=1;
    dfs(cnt);
    for(int i=1;i<=k;i++)
    {
        int l,r;
        read(l),read(r);
        writeln(lca(l,r));
    }
    return 0;
}

点分治

点分治(1·针对裸题)

luogu P3806 【模板】点分治1

题目描述

给定一棵有n个点的树
询问树上距离为k的点对是否存在。
输入格式:
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出格式:
对于每个K每行输出一个答案,存在输出“AYE”,否则输出”NAY”(不包含引号)

传送门

分析:

我们先定义一些变量:

int n,m,flag;
struct edge{int from,to,cost;}bian[N];
int head[N],tot,sum,root;//sum是子树的总点数,root为根。
int max_son[N],son[N];//max_son是子树的最大集,son为以i为根的子树节点。
bool vis[N],k_ans[100000010];//访问标记,k_ans为k是否存在。
int rode[N];//i到根的距离。
struct node {int ancestors,cost;}dian[N];//ancestors,表示点i除根以外的最浅祖先,cost表示到根的代价。

然后我们要往图里加入点:( 这非常简单)

void add(int l,int r,int k){bian[++tot]=(edge){head[l],r,k};head[l]=tot;}

然后我们要找重心,如果不利用重心对代码进行优化,复杂度可能变大,本蒟蒻就不解释了。找重心只要遍历整棵树,找到所有节点中儿子大小最大值最小的点就是重心,代码中用root表示。

void find_root(int now,int fa)//递归找重心。
{
    son[now]=1,max_son[now]=0;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]||next==fa)
            continue;
        find_root(next,now);
        son[now]+=son[next];
        max_son[now]=max(max_son[now],son[next]);
    }
    max_son[now]=max(max_son[now],sum-son[now]);
    if(max_son[now]<max_son[root])
        root=now;
}

然后,就到了整个代码的核心,点分治。我们已知暴力枚举长度,复杂度爆炸,然而,如果我们每次找到这棵树的重心,O(n)遍历棵树,找到每个节点到根的cost,最后暴利把两条位于不同子树的链组合起来,更新k ans数组就好了。接着就删去现在的根节点,找到剩下子树的重心,重复上面的操作就好了,复杂度大概是n logn^2
下面是完整代码:

#include<bits/stdc++.h>
using namespace std;
const LL N=2e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n,m,flag;
struct edge{int from,to,cost;}bian[N];
int head[N],tot,sum,root;//sum是子树的总点数,root为根。
int max_son[N],son[N];//max_son是子树的最大集,son为以i为根的子树节点。
bool vis[N],k_ans[100000010];//访问标记,k_ans为k是否存在。
int rode[N];//i到根的距离。
struct node {int ancestors,cost;}dian[N];
void add(int l,int r,int k){bian[++tot]=(edge){head[l],r,k};head[l]=tot;}
void find_root(int now,int fa)//递归找重心。
{
    son[now]=1,max_son[now]=0;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]||next==fa)
            continue;
        find_root(next,now);
        son[now]+=son[next];
        max_son[now]=max(max_son[now],son[next]);
    }
    max_son[now]=max(max_son[now],sum-son[now]);
    if(max_son[now]<max_son[root])
        root=now;
}
int tot_anss;
void solve_dfs(int now,int zuxian,int fa)
{
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]||fa==next)
            continue;
        rode[next]=rode[now]+bian[i].cost;
        dian[++tot_anss]=(node){zuxian,rode[next]};
        solve_dfs(next,zuxian,now);
    }
}
void find_k(int now)
{
    rode[now]=0,tot_anss=0;
    vis[now]=1;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]==1)
        continue;
        rode[next]=bian[i].cost;
        dian[++tot_anss]=(node){next,rode[next]};
        solve_dfs(bian[i].to,bian[i].to,now);
    }
    for (int i=1;i<=tot_anss;i++) k_ans[dian[i].cost]=1;
    for(int i=1;i<=tot_anss;i++)
        for(int j=i+1;j<=tot_anss;j++)
        if(dian[i].ancestors!=dian[j].ancestors)
            k_ans[dian[i].cost+dian[j].cost]=1;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(!vis[next])
        {
            max_son[0]=inf;
            root=0;
            sum=son[next];
            find_root(next,0);
            find_k(root);
        }
    }
}
int main()
{
    read(n),read(m);
    for(int i=1;i<n;i++)
    {
        int l,r,k;
        read(l),read(r),read(k);
        add(l,r,k);add(r,l,k);
    }
    sum=max_son[0]=n,root=0;//root必须更新。
    find_root(1,0);
    find_k(root);
    for(int i=1;i<=m;i++)
    {
        read(flag);
        if(k_ans[flag]==1)
            printf("AYE\n");
        else
            printf("NAY\n");
    }
    return 0;
}

day2 luogu P2634 [国家集训队]聪聪可可

分析:

这道题就是在上题的模板上,把统计k改成%3就好了,所以k_ans数组就没用了,但刚开始,我边的数组开小了,所以wa了一发。
###代码如下:

#include<bits/stdc++.h>
using namespace std;
const LL N=2e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n,m,flag;
struct edge{int from,to,cost;}bian[N*2];
int head[N],tot,sum,root;//sum是子树的总点数,root为根。
int max_son[N],son[N];//max_son是子树的最大集,son为以i为根的子树节点。
bool vis[N];//访问标记,k_ans为k是否存在。
int rode[N],ans;//i到根的距离。
struct node {int ancestors,cost;}dian[N];
inline void add(int l,int r,int k){bian[++tot]=(edge){head[l],r,k};head[l]=tot;}
inline void find_root(int now,int fa)//递归找重心。
{
    son[now]=1,max_son[now]=0;
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(vis[next]||next==fa)
            continue;
        find_root(next,now);
        son[now]+=son[next];
        max_son[now]=max(max_son[now],son[next]);
    }
    max_son[now]=max(max_son[now],sum-son[now]);
    if(max_son[now]<max_son[root])
        root=now;
}
int tot_anss;
inline void solve_dfs(int now,int zuxian,int fa)
{
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(vis[next]||fa==next)
            continue;
        rode[next]=rode[now]+bian[i].cost;
        dian[++tot_anss]=(node){zuxian,rode[next]};
        solve_dfs(next,zuxian,now);
    }
}
inline void find_k(int now)
{
    rode[now]=0,tot_anss=0;
    vis[now]=1;
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(vis[next]==1)
            continue;
        rode[next]=bian[i].cost;
        dian[++tot_anss]=(node){next,rode[next]};
        solve_dfs(bian[i].to,bian[i].to,now);
    }
    for (register int i=1;i<=tot_anss;i++) 
        if(dian[i].cost%3==0) 
            ans++;
    for(register int i=1;i<=tot_anss;i++)
        for(register int j=i+1;j<=tot_anss;j++)
            if(dian[i].ancestors!=dian[j].ancestors)
                if((dian[i].cost+dian[j].cost)%3==0)
                    ans++;
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(!vis[next])
        {
            max_son[0]=inf;
            root=0;
            sum=son[next];
            find_root(next,0);
            find_k(root);
        }
    }
}
main()
{
    read(n);
    for(register int i=1;i<n;i++)
    {
        register int l,r,k;
        read(l),read(r),read(k);
        add(l,r,k);add(r,l,k);
    }
    sum=max_son[0]=n,root=0;//root必须更新。
    find_root(1,0);
    find_k(root);
    int zz=n*n;
    ans*=2;
    ans+=n;
    int gcd=__gcd(zz,ans);
    printf("%d/%d\n",ans/gcd,zz/gcd);
    return 0;
}

好久没写博客了,如有错误,请留言。

SAM乱讲

emmm,对着陈立杰的ppt,打这篇博客。。。不是很懂,所以你们将就着看吧。。。。

我们先来讲一些定义:

  • 妨令trans(s,ch)表示当前状态是s,在读入字符ch之后,所到达的状态。
  • 同时令trans(s,str)表示当前状态是s,在读入字符串str之后,所到达的状态。
  • 从状态s开始可以识别的字符串,就是所有使得trans(s,x)属于end的字符串,名为Reg(s)

我们定义后缀自动机:(给定字符串S)

  • S的后缀自动机suffix automaton(以后简记为SAM)是一个能够识别S的所有后缀的自动机。
  • 即SAM(x) = True,当且仅当x是S的后缀。
  • 同时后面可以看出,后缀自动机也能用来识别S所有的子串。

由于直接把所有后缀加入Trie树中,节点大概有N^2个,这样太多了,所以我们引入最简状态后缀自动机

  • 我们令ST(str)表示trans(init,str)。就是初始状态开始读入字符串str之后,能到达的状态。
  • 令字符串为S,他的后缀集合为Suf,他的连续子串的集合为Fac
  • 从位置a开始的后缀为Suffix(a),S[l,r)表示区间[l,r)构成的子串,下标从0开始

我们不能对每一个s属于Fac的串都建一个状态,这样存不下,所以我们考虑ST(s)可以识别多少子串,就是Reg(ST(a));字符串x能被识别,仅当x属于Suf。。对于每一个状态s,我们只关心Reg(s);

假设有字符串a在S中的[l,r)范围中出现,那么由于自动机的特点,他就可以识别从r到结尾的后缀;我们假设a在S中出现的集合是{[l1,r1),[l2,r2),…,[ln,rn)};那么Reg(ST(a))就是{Suffix(r1),Suffix(r2),….Suffix(rn)}这个集合。所以我们不妨令Right(x)={r1,r2,…,rn}那么Reg(ST(x))就完全由Right(x)决定了;

由此可知对于两个子串a,b属于Fac,如果Right(a)=Right(b),那么ST(a)=ST(b);所以一个状态s,由所有Right集合是Right(s)的字符串组成。。。(我已经晕了)所以只要给定一个长度,就可以通过Right集合求出字符串。。。因为某些原因我们令s的区间为[Min(s),Max(s)]。。。

接下来我们讲一下为什么要这么写:

这样写的好处是优化了状态数,我们来证明一下,这样的状态数是线性的。。。

我们考虑两个状态a,b,他们的Right集合为Ra,Rb。我们假设Ra和Rb有交集,不妨设r属于RaRb的交集。那么由于a和b表示的子串不会有交集所以[Min(a),Max(a)]和[Min(b),Max(b)]不会有交集假设Max(a)<Max(b),那么a中的所有子串长度都比b中短,由于都是往前算后缀的。那么a的所以串都是b的后缀,所以Ra属于Rb。这样看来两个串的Right集合,要么不相交,要么一个是另一个的真子集。。。

a

从上图我们可以看出Right集合其实构成一个树状结构,我们称它为Parent树。。。易得这个树的大小一定是O(n)的。令一个状态s,我们令fa=Parent(s)表示上面的那个图中他的父亲,那么Right(s)属于Right(fa),而且Right(fa)的大小是其中最小的。考虑长度,s的范围,[Min(s),Max(s)],为什么Min(s)-1不符合要求,肯定是因为出现的地方超过了Right(s),同时随着长度的减小,出现的地方越来越多,那么Min(s)-1就必然属于fa的范围,那么Max(fa)=Min(s)-1;

然后我们来讲一下他的一些性质:

那么令状态数为M,成树中的边最多只有M-1条,接下来考虑非树边。对于一条非树边a→b标号为c
中我们构造:生成树中从根到状态α的路径+(a->b)+b到任意一个end状态。
可以发现这是一条从init到end状态的路径,由于这是一个识别所有后缀的后缀自动机,因此这必然是一个后缀。那么一个非树边可以对应到多个后缀,我们对每个后缀,沿着自动机走,将其对应上经过的第一条非树边。那么每个后缀最多对应一个非树边,同时一个非树边至少被一个后缀所对应,所以非树边的数量不超过后缀数。。。
所以边的数量也不会超过O(N)。。。

子串的性质:

  • 由于每个子串都必然包含在SAM的某个状态里。
  • 那么一个字符串s是S的子串,当且仅当,ST(s)!=null
  • 那么我们就可以用SAM来解决子串判定问题。
  • 同时也可以求出这个子串的出现个数,就是所在状态Right集合的大小。
  • 在一个状态中直接保存Right集合会消耗过多的空间,我们可以发现状态的Right就是它Parent树中所有孩子Right集合的并集,进一步的话,就是Parent树中它所有后代中叶子节点的Right集合的并集。
  • 那么如果按dfs序排列,一个状态的right集合就是一段连续的区间中的叶子节点的Right集合的并集,那么我们也就可以快速求出一个子串的所有出现位置了。
  • 树的dfs序列:所有子树中节点组成一个区间。

讲完了这些,我们开始构造自动机:

我们每次添加一个字符,并且更新当前的SAM使得它成为包含这个新字符的SAM。令当前字符串为T,新字符为x令T的长度为L。中SAM(T)→SAM(Tx)那么我们新增加了一些子串,它们都是串Tx的后缀.Tx的后缀,就是7的后缀后面添一个x/那么我们考虑所有表示T的后缀(也就是 Right集合中包含L)的节点v1,v2,v3)。由于必然存在一个 Right(p)={L}的节点p(ST(T))。那么v1,v2,…,vk由于 Right集合都含有L,那么它们在 Parent/树中必然全是p的祖先。可以使用 Parentp函数找到他们。

同时我们添加一个字符x后,令np表示ST(Tx),则Right(np)={L+1}.不妨让他们从后代到祖先排为v1=p,v2,…,vk=root。考虑其中一个v的 Rights集合=(r1,r2,…,rn=L}。那么在它的后面添加一个新字符x的话,形成新的状态nv的话,只有S[ri]=x的ri那些是符合要求的。

同时在之前我们知道,如果从v出出发没有标号为x的边(我们先不看rn),那v的 Right集合内就没有满足这个要求的ri。那么由于v1,v2,v3的 Right的集合逐渐扩大,如果vi出发有标号为x的边,那么vi+1出发也肯定有。对于出发没有标号为x的边的v,它的 Right集合内只有rn是满足要求的,所以根据之前提到的转移的规则,让它连一条到np标号为x的边。

令vp为v1,v2,…,vk中第一有标号为x的边的状态。考虑vp的Right集合=(r1,r2,…,rn},令 trans(vp,x)=q。那么q的Rght集合就是{ri+1},S[ri]=x的集合(注意到这是更新之前的情况,所以rn是不算的)。注意到我们不一定能直接在q的Right集合中插入L+1.

最后一个是x,用红色画出vp的结東位置上,长度为Max(vp)的串
用蓝色画出q的结東位置上,长度为Max(q)的串。
串: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAAAAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx
中从这里可以看出,如果在Right(q)中强行插入L+1,会导到致Max(q)变小,而引发一系列的间题。
当然如果Max(q)=Max(vp)+1就不会有这样的问题,直接插入即可,我们只要让 Parent(np)=q,就可以结東这个阶段了。

这个时候,我们注意到q实际上被分成了两份
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAAAAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx
AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx
那么我们新建一个节点nq,使 Right(ng)=Riht(q)∩{L+1}。同时可以看出Max(nq)=MX(vp)+1。那么由于 Right(q)是 Right(nq)的真子集,所以 Parent(q))=nq。同时 Parent(np)=nq。并且容易证明 Parent(nq)= Parent(q)(原来的)

接下来考虑节点nq,在转移的过程中结束位置L+1是不起作用的,所以trans(nq)就跟原来的trans(q)是一样的,直接拷贝就好了。。。

接下来,如果新建了节点nq我们还得处理。
回忆:v1,v2,…,vk是所有Right集合包含的节点按后代到祖先排序,其中vp是第一个有标号为x的边的祖先。x是这轮新加入的字符。由于vp,…,vk都有标号为x的边,并且到达的点的Right集合,随着出发点Right集合的变大,也会变大,那么只有一段vp,…,ve,通过标号为x的边,原来是到结点q的。
q=Trans(vp,x);
那么由于在这里q节点已经被替换成了nq,我们只要把vp,…,ve的 Irans(*,x)设为nq即可。

然后转移就写完了。。。

令当前串为T,加入字符为x。令p=ST(T), Right(p)= {Length(T)}的节点。新建np=ST(Tx),Right(np)= {Length(T)+1}的节点。对p的所有没有标号x的边的祖先v, trans(v,x)=np。找到p的第一个祖先vp,它有标号x的边,如果没有这样的
vp,那么 Parent(p)=root,结束该阶段。令q= trans(vp,x),若Max(q)=Max(vp)+1,令 Parent(np)=q,结束该阶段。否则新建节点nq,trans(nq,*)=trans(q,*)。
Parent(nq) = Parent(q) (先前的);    Parent(q) = nq;Parent(np)=nq
对所有trans(v,x) == q的p的祖先v,trans(v,x) 改成nq.

c++ 核心代码。。。

struct State
{
    State *par, *go[26];
    int val;
    State(int _val):
        par(0),next(0),val(_val){
            memset(go,0,sizeof(go));
        }
};
State *root,*last;
void extend(int w)
{
    State *p=last;
    State *np = new State(p->val+1);
    while(p && p->go[w]==0)
        p->go[w]=np,p=p->par;
    if(p == 0)
        np->par =root;
    else
    {
        State *q=p->go[w];
        if(p->val+1==q>val)
            np->par=q;
        else
        {
            State *nq =new State(p->val+1);
            memcpy(nq->go,q->go,sizeof(q->go));
            nq->par = q->par;
            q->par = nq;
            np->par = nq;
            while(p && p->go[w]==q)
                p->go[w] = nq,p = p->par;
        }
    }
    last=np;
}

然后终于搞完了,你们随便看看,然后点个赞就好了。。。

平衡树讲解

前言:

今天想把之前写的无旋heap讲一下。。。

平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了。它可以利用随机化来保证树的平衡,就是左右子树大小差不多,在查询时可以优化复杂度。。。

比如来看落谷这道普通平衡树的模板题:

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  • 插入 x 数
  • 删除 x 数(若有多个相同的数,因只删除一个)
  • 查询 x 数的排名(排名定义为比当前数小的数的个数 +1+1+1 。若有多个相同的数,因输出最小的排名)
  • 查询排名为 x 的数
  • 求 x 的前驱(前驱定义为小于 x ,且最大的数)
  • 求 x 的后继(后继定义为大于 x ,且最小的数)

时空限制:1000ms,128M

1.n的数据范围: n≤100000

2.每个数的数据范围:[-1000000,10000000]

看起来是不是很简单…..

一看这道题就是数据结构,又正好满足我们平衡树的要求。。。那我们开始讲平衡树。。。

首先我们定义这课树

struct Node
{
    int key,p,size;
    Node *ch[2];
}*root;

key用来存当前点的值,p用来存随机树,size顾名思义存树的大小,而ch则是存儿子(这是一棵二叉树,所以只有两个儿子)。。。

由于我用的是指针,所以我们还要写一个申请指针空间,以及初始化的函数。。。如下。。。

Node *new_node(int x)
{
    Node *y=new Node;
    y->key=x;y->p=rand();
    y->ch[0]=y->ch[1]=NULL;
    y->size=1;
    return y;
}

当然还有我们询问指针对应的值了,为了防止re我又写了两个函数(别问我为什么这么烦,用什么指针,因为是学长教的。。。)

inline int key_of(Node *x)
{
    if(x==NULL)
        return 0;
    else
        return x->key;
}
inline int size_of(Node *x)
{
    if(x==NULL)
        return 0;
    else
        return x->size;
}

然后就到了我们平衡树的关键操作了,他叫merge(表合并),用处是把两棵树合在一起,由于平衡树的中序遍历是原来的串,所以这个merge怎么写就令人深思了,显然我们传入两棵树的根指针,如果其中有一棵树是空的明显可以返回另一颗,如果两棵都不为空,那么我们比较随机化的p值,p在这里的作用就是选择当父亲的树根,我们假设p大的A当父亲,那么我们就把另一棵树B连到当前树A上,然后A树的儿子和树B。。。最后返回树的根,由于指针的作用,就是返回了合并好的树。。。

Node *merge(Node *x,Node *y)
{
    if(x==NULL)
        return y;
    if(y==NULL)
        return x;
    if(x->pp)
    {
        x->ch[1]=merge(x->ch[1],y);
        update(x);
        return x;
    }
    else
    {
        y->ch[0]=merge(x,y->ch[0]);
        update(y);
        return y;
    }
}

然后聪明的你是不是发现了,merge函数里还有一个函数没有定义,叫update,他的作用是更新父亲节点的值。。。在这个题目中他只要更新size就好了,在其他题目中还可以用来更新什么sum之类的值。。。所以很短。。。

inline void update(Node *x)
{
    x->size=size_of(x->ch[0])+size_of(x->ch[1])+1;
}

然后又到了一个关键函数,叫split,他的作用是把一棵树分裂成两棵,由于题目原因,我们既要可以按key值分裂,也可以按照位置分裂,他的过程有点向merge的逆过程。。。比如按照key值分裂,若左儿子的值小于询问,那么我们就去查找右儿子,然后递归下去,由于指针指向地址,我们做的操作可以连接上去打起来也很简单。。。

void split_k(Node *now,Node *&x,Node *&y,int k)
{
    if(now==NULL)
    {
        x=NULL,y=NULL;
        return;
    }
    if(size_of(now->ch[0])+1ch[1],now->ch[1],y,k-size_of(now->ch[0])-1);
    }
    else
    {
        y=now;
        split_k(now->ch[0],x,now->ch[0],k);
    }
    update(now);
}
void split_key(Node *now,Node *&x,Node *&y,int key)
{
    if(now==NULL)
    {
        x=NULL,y=NULL;
        return;
    }
    if(key_of(now)ch[1],now->ch[1],y,key);
    }
    else
    {
        y=now;
        split_key(now->ch[0],x,now->ch[0],key);
    }
    update(now);
}

主要的函数都打完了,下面就开始打各类操作了,因为太简单我就举个例子。。。

比如你要合并两棵树:

root=merge(x,y)//x,y都要是一棵定义过得树

比如你以k值要分裂一颗树:

split_key(root,x,y,k);//这里的x,y与上面的同理。。。

然后就讲完了。。。现在贴一个全代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e7+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO 
{
    template inline void read(tp &x) 
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<p=rand();
        y->ch[0]=y->ch[1]=NULL;
        y->size=1;
        return y;
    }
    inline int key_of(Node *x)
    {
        if(x==NULL)
            return 0;
        else
            return x->key;
    }
    inline int size_of(Node *x)
    {
        if(x==NULL)
            return 0;
        else
            return x->size;
    }
    inline void update(Node *x)
    {
        x->size=size_of(x->ch[0])+size_of(x->ch[1])+1;
    }
    Node *merge(Node *x,Node *y)
    {
        if(x==NULL)
            return y;
        if(y==NULL)
            return x;
        if(x->pp)
        {
            x->ch[1]=merge(x->ch[1],y);
            update(x);
            return x;
        }
        else
        {
            y->ch[0]=merge(x,y->ch[0]);
            update(y);
            return y;
        }
    }
    void split_k(Node *now,Node *&x,Node *&y,int k)
    {
        if(now==NULL)
        {
            x=NULL,y=NULL;
            return;
        }
        if(size_of(now->ch[0])+1ch[1],now->ch[1],y,k-size_of(now->ch[0])-1);
        }
        else
        {
            y=now;
            split_k(now->ch[0],x,now->ch[0],k);
        }
        update(now);
    }
    void split_key(Node *now,Node *&x,Node *&y,int key)
    {
        if(now==NULL)
        {
            x=NULL,y=NULL;
            return;
        }
        if(key_of(now)ch[1],now->ch[1],y,key);
        }
        else
        {
            y=now;
            split_key(now->ch[0],x,now->ch[0],key);
        }
        update(now);
    }
    Node *x,*y,*z,*w,*q,*p;
}
using namespace Treap;
int T;
int main() 
{
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        switch(l)
        {
            case 1:
                split_key(root,x,y,r);
                x=merge(x,new_node(r));
                root=merge(x,y);
                break;
            case 2:
                split_key(root,x,y,r);
                split_key(x,z,w,r-1);
                split_k(w,q,p,1);delete q;
                z=merge(z,p);
                root=merge(z,y);
                break;
            case 3:
                split_key(root,x,y,r-1);
                printf("%d\n",size_of(x)+1);
                root=merge(x,y);
                break;
            case 4:
                split_k(root,x,y,r);
                split_k(x,z,w,r-1);
                printf("%d\n",key_of(w));
                x=merge(z,w);
                root=merge(x,y);
                break;
            case 5:
                split_key(root,x,y,r-1);
                split_k(x,z,w,size_of(x)-1);
                printf("%d\n",key_of(w));
                x=merge(z,w);
                root=merge(x,y);
                break;
            case 6:
                split_key(root,x,y,r);
                split_k(y,z,w,1);
                printf("%d\n",key_of(z));
                y=merge(z,w);
                root=merge(x,y);
                break;
        }
    }
    return 0;
}

哈哈哈,讲完了,你可以点关注了。。。
溜了溜了。。。