头像

Noe1017

中北大学




离线:33分钟前


最近来访(483)
用户头像
目标大佬的大学生
用户头像
肥肠煎蛋
用户头像
こんにちは
用户头像
Anoxia._4
用户头像
AcWing2AK
用户头像
蜉蝣
用户头像
Darren_4
用户头像
222222
用户头像
柒月栗子
用户头像
815741912
用户头像
重生之幻影
用户头像
rsy
用户头像
数论贪心图论DP通通不会
用户头像
Rw-chen
用户头像
ζޓއ๓o北上少年
用户头像
Rookie_
用户头像
yao云
用户头像
follow_my_dream
用户头像
whale77
用户头像
Nminem


Noe1017
5天前

树上差分有多种写法.

写法一:直接对于所有深度的链单独进行处理:

Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int id[N],a[N],sum[N];
int e[2*N],ne[2*N],idx,h[2*N];
void add(int a,int b)
{
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int fa,int depth)
{
        id[depth]=u;
        sum[id[max(0,depth-a[u]-1)]]--;
        sum[u]++; 
        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==fa)continue;
                dfs1(j,u,depth+1);
        }
}
int ans[N];
int dfs2(int u,int fa)
{
        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==fa)continue;
                sum[u]+=dfs2(j,u);
        }
        return sum[u];
}
void solve()
{
       memset(h,-1,sizeof h);
       int n;cin>>n;
       for(int i=1;i<n;i++)
       {
               int x,y;
               cin>>x>>y;
               add(x,y),add(y,x);
       }
       for(int i=1;i<=n;i++)cin>>a[i];
       dfs1(1,-1,1); 
       dfs2(1,-1);
       for(int i=1;i<=n;i++)cout<<sum[i]<<' ';
       cout<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
  //      freopen("test.in","r",stdin);
        solve();
        return 0;
}

写法二:倍增法,求出每个点对应的链上祖先.

Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int a[N],sum[N];
int e[2*N],ne[2*N],idx,h[2*N];
int fa[N][21];
void add(int a,int b)
{
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int father,int depth)
{
        fa[u][0]=father;
        for(int k=1;k<=20;k++)fa[u][k]=fa[fa[u][k-1]][k-1];

        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==father)continue;
                dfs1(j,u,depth+1);
        }
}//倍增 
int dfs2(int u,int father)
{
        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==father)continue;
                sum[u]+=dfs2(j,u);
        }
        return sum[u];
}
void solve()
{
       memset(h,-1,sizeof h);
       int n;cin>>n;
       for(int i=1;i<n;i++)
       {
               int x,y;
               cin>>x>>y;
               add(x,y),add(y,x);
       }
       for(int i=1;i<=n;i++)cin>>a[i];

       //注意dfs和倍增的顺序 
       dfs1(1,0,1);
       for(int i=1;i<=n;i++)
       {
               int x=i,y=i;
               for(int k=20;k>=0;k--)
                if(a[i]>>k&1)y=fa[y][k];

                y=fa[y][0];
                sum[i]++,sum[y]--;
       }
       dfs2(1,0);
       for(int i=1;i<=n;i++)cout<<sum[i]<<' ';
       cout<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    //    freopen("test.in","r",stdin);
        solve();
        return 0;
}




Noe1017
8天前

传送门

DFS序基础

思路:

先建立$Fail$树.并得到$Fail$树的$DFS$序
对于查询可以分析得知:每次查询的答案就是当前指针到根节点的$fail$链上的标记数量.
对于修改可以分析得知:每次修改以后Fail树上一点$u$,只会对子树到$root$的$fail$链的答案产生响.

因此可以将查询修改 转化成:区间修改和单点查询.
每次修改的时候就相当于修改子树.
每次查询的时候用相当于树状数组维护了树上差分.
单点查询的时候就等价求区间和

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],idx,h[N];
int cnt[N],tr[N][26],q[N],fail[N];
struct Query{
        string s;
        int type,id;
}query[N];
int n,m,tot;
void add(int a,int b)
{
        e[tot]=b,ne[tot]=h[a],h[a]=tot++;
}
int insert(string s)
{
        int p=0;
        for(int i;s[i];i++)
        {
                int u=s[i]-'a';
                if(!tr[p][u])tr[p][u]=++idx;
                p=tr[p][u];
        }
        cnt[p]++;
        return p;//建树 
}
void build()
{
        int hh=0,tt=0;
        for(int i=0;i<26;i++)
         if(tr[0][i])
         {
                 q[tt++]=tr[0][i];
                 add(0,tr[0][i]);
         }

        while(hh!=tt)
        {
                int t=q[hh++];
                for(int i=0;i<26;i++)
                {
                        int u=tr[t][i];
                        if(!u)tr[t][i]=tr[fail[t]][i];
                        else
                        {
                                fail[u]=tr[fail[t]][i];
                                add(fail[u],u);//建fail树 
                                q[tt++]=u;
                        }
                }
        }
}
int dfn[N],R[N],timestamp;
void dfs(int u)
{
        R[u]=timestamp,dfn[u]=timestamp++;
        for(int i=h[u];~i;i=ne[i])
        {
             int j=e[i];
             dfs(j);
             R[u]=R[j];  //更新子树中最大时间戳      
        } 
}
int sum[N];
int lowbit(int x){return x&-x;};
void modify(int x,int c)
{
        for(int i=x;i<=idx;i+=lowbit(i))sum[i]+=c;
}
int cal(int x)
{
        int res=0;
        for(int i=x;i>0;i-=lowbit(i))res+=sum[i];
        return res;
}
int get(string s)
{
        int res=0;
        int u=0;
        for(int i=0;s[i];i++)
        {
                int t=s[i]-'a';
                u=tr[u][t];
                res+=cal(dfn[u]);
        }
        return res;
}
void init()
{
        tot=idx=timestamp=0;
        memset(h,-1,sizeof h);
        memset(tr,0,sizeof tr);
        memset(cnt,0,sizeof cnt);
        memset(fail,0,sizeof fail);
        memset(dfn,0,sizeof dfn);
        memset(R,0,sizeof R);
        memset(sum,0,sizeof sum);
}
void solve()
{
       cin>>n>>m;
       init();
       for(int i=0;i<n;i++)
       {
            string s;cin>>s;
            insert(s);
       } 
       for(int i=1;i<=m;i++)
       {
               cin>>query[i].type>>query[i].s;
               if(query[i].type==1)
               {
                       query[i].id=insert(query[i].s);
                       cnt[query[i].id]--;
               }
       }
       build();
       dfs(0); 
       for(int i=0;i<idx;i++)
        if(cnt[q[i]])modify(dfn[q[i]],1),modify(R[q[i]]+1,-1);

       for(int i=1;i<=m;i++)
        if(query[i].type==1)cnt[query[i].id]++,modify(dfn[query[i].id],1),modify(R[query[i].id]+1,-1);
        else  cout<<get(query[i].s)<<endl;

       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}



分享 整除分块

Noe1017
15天前

D2. Chopping Carrots (Hard Version)

思路:

首先用整数分块将每一个点的所有可能取值处理出来.
然后利用整数分块 是连续递减的性质,每次我们为一个可能最小值$v$维护一个最大上界$m[v]$.
最后由于所有可能的最小值一定是不超过$a[1]$的因此我们暴力枚举$a[1]$的所有值并利用$m$数组的前缀最大值即$m[v]$的最大上界.遍历后就可以得到答案。

注意:由于我们用的是整数分块也就是,所有$\frac{a_i}{p_i}$的可能,因此所有维护的$m[v]$的最大上界得到的答案一定是当$v$取到我们的$\frac{a_i}{p_i}$才会是最佳答案.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,k;
int a[N],mx[N]; 
void get(int x)//整除分块 
{
        int l=1,r=0;
        int res=inf,maxv=min(x,k);
        while(l<=maxv)
        {
                int cnt=x/l;
                r=x/(x/l);//求出分块的右边界 
                mx[cnt+1]=max(mx[cnt+1],res);
                l=r+1;
                res=cnt;
        }
        mx[0]=max(mx[0],res);//
}
void init()
{
        for(int i=1;i<=n;i++)get(a[i]);

        int ans=1e9;
        int cm=0;
        for(int i=0;i<=a[1];i++)
        {
                cm=max(cm,mx[i]);
                ans=min(ans,cm-i);
        }
        cout<<ans<<endl;
        return ;
}
void solve()
{
       cin>>n>>k;
       memset(mx,0,sizeof mx);
       for(int i=1;i<=n;i++)cin>>a[i];
       sort(a+1,a+1+n);
       n=unique(a+1,a+1+n)-a-1;

       init();
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}

整除分块模板:

Code:

void get(int x)//整除分块 
{
        int l=1,r=0;
        int res=inf,maxv=min(x,k);
        while(l<=maxv)
        {
                int cnt=x/l;
                r=x/(x/l);//求出分块的右边界 
                mx[cnt+1]=max(mx[cnt+1],res);
                l=r+1;
                res=cnt;
        }
        mx[0]=max(mx[0],res);//
}



Noe1017
16天前

传送门

思路:经典带树刨的Dsu on the tree

1.先树链刨分.
2.然后对每一个节点

首先暴力枚举并计算所有轻儿子的答案和贡献并清除
然后计算重儿子的答案和贡献并保留.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],idx,h[N];
void add(int a,int b)
{
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int ans[N];
int n,m,col[N],cnt[N];
int sum,flag;
int sz[N],son[N];
void dfs1(int u,int father)
{
        sz[u]=1;
        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==father)continue;
                dfs1(j,u);
                sz[u]+=sz[j];
                if(sz[son[u]]<sz[j])son[u]=j;
        }
}
void count(int u,int fa,int val)
{
       if(!cnt[col[u]])sum++;
       cnt[col[u]]+=val;

       for(int i=h[u];~i;i=ne[i])
       {
               int j=e[i];
               if(j==fa||j==flag)continue;
               count(j,u,val);
       }
}
void dfs2(int u,int fa,bool state)
{
        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==fa||j==son[u])continue;
                dfs2(j,u,false);
        }
        if(son[u])
        {
                dfs2(son[u],u,true);
                flag=son[u];//标志字段 
        }
        count(u,fa,1);//
        flag=0;
        ans[u]=sum;
        if(!state)
        {
                count(u,fa,-1);
                sum=0;
        }
}
void solve()
{
       memset(h,-1,sizeof h);
       int n,m;
       cin>>n>>m;
       for(int i=1;i<=n;i++)cin>>col[i];

       for(int i=1;i<=n-1;i++)
       {
               int u,v;
               cin>>u>>v;
               add(u,v),add(v,u);
       }
       dfs1(1,-1);
       dfs2(1,-1,0);

     //  for(int i=1;i<=n;i++)cout<<i<<' '<<son[i]<<endl;

       while(m--)
       {
               int x;cin>>x;
               cout<<ans[x]<<endl;
       }
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    //    freopen("test.in","r",stdin);
        solve();
        return 0;
}

时间复杂度:$O(n*logn)$

板子Code:

void dfs1(int u,int father)
{
        sz[u]=1;
        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==father)continue;
                dfs1(j,u);
                sz[u]+=sz[j];
                if(sz[son[u]]<sz[j])son[u]=j;
        }
}
void count(int u,int fa,int val)
{
       if(!cnt[col[u]])sum++;
       cnt[col[u]]+=val;

       for(int i=h[u];~i;i=ne[i])
       {
               int j=e[i];
               if(j==fa||j==flag)continue;
               count(j,u,val);
       }
}
void dfs2(int u,int fa,bool state)
{
        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==fa||j==son[u])continue;
                dfs2(j,u,false);
        }
        if(son[u])
        {
                dfs2(son[u],u,true);
                flag=son[u];//标志字段 
        }
        count(u,fa,1);//
        flag=0;
        ans[u]=sum;
        if(!state)
        {
                count(u,fa,-1);
                sum=0;
        }
}



Noe1017
17天前

E. Qpwoeirut and Vertices

思路:
1.克鲁斯卡尔重构树,重构以后可以发现从任意两点可达的最大边序号就是重构树多点LCA的点权.
2.用ST表维护区间DFS序最大值和最小值.
3.多点LCA结论:

结论.jpg

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=4e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],idx,h[N],w[N];
int n,m,q,dep[N],cnt,fa[N][64],p[N];
int dfn[N],maxv[N][32],minv[N][32],id[N],num,root;
void add(int a,int b)
{
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int find(int x)
{
        return p[x]==x?x:p[x]=find(p[x]);
}
void init()
{

     for(int j=0;j<=(int)log2(n);j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
       if(!j)maxv[i][j]=dfn[i];
       else maxv[i][j]=max(maxv[i][j-1],maxv[i+(1<<(j-1))][j-1]);

     for(int j=0;j<=(int)log2(n);j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
       if(!j)minv[i][j]=dfn[i];
       else minv[i][j]=min(minv[i][j-1],minv[i+(1<<(j-1))][j-1]);
}
struct Edge{
        int u,v,val;
        bool operator <(const Edge &a)const
        {
                return val<a.val;
        }
}edge[N];
void ex_kruskal()
{
        sort(edge+1,edge+1+m);
        num=n,root=0,cnt=0;
        for(int i=1;i<=2*n;i++)p[i]=i,h[i]=-1,w[i]=0;

        for(int i=1;i<=m;i++)
        {
                int x=find(edge[i].u),y=find(edge[i].v);
                if(x!=y)
                {
                        p[x]=p[y]=++num;
                        root=max(root,num);
                        w[num]=edge[i].val;
                        add(num,x),add(x,num);
                        add(num,y),add(y,num);
                }
        }
}
void dfs(int u,int father,int depth)
{
        dep[u]=depth,dfn[u]=++cnt,id[dfn[u]]=u;

        if(u!=root)
        {
                fa[u][0]=father;
                for(int k=1;k<=32;k++)fa[u][k]=fa[fa[u][k-1]][k-1];
        }

        for(int i=h[u];~i;i=ne[i])
        {
                int j=e[i];
                if(j==father)continue;
                dfs(j,u,depth+1);
        }
}
int lca(int x,int y)
{
        if(dep[x]<dep[y])swap(x,y);

        for(int i=32;i>=0;i--)
         if(dep[fa[x][i]]>=dep[y])x=fa[x][i];

        if(x==y)return x;

        for(int i=32;i>=0;i--)
         if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        return fa[x][0];
}
void solve()
{
       cin>>n>>m>>q;

       for(int i=1;i<=m;i++)
       {
               int u,v;
               cin>>u>>v;
               edge[i]={u,v,i};
       }
       ex_kruskal();
       dfs(root,-1,1);
       init();//维护区间 Dfs 的最大值和最小值 
       while(q--)
       {
               int l,r;
               cin>>l>>r;//
               int len=(int)log2(r-l+1); 
               int Max=max(maxv[l][len],maxv[r-(1<<len)+1][len]);
               int Min=min(minv[l][len],minv[r-(1<<len)+1][len]);

               int anc=lca(id[Min],id[Max]);
               cout<<w[anc]<<' ';
       }
       cout<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}

克鲁斯卡尔重构树 模板:

struct Edge{
        int u,v,val;
        bool operator <(const Edge &a)const
        {
                return val<a.val;
        }
}edge[N];
void ex_kruskal()
{
        sort(edge+1,edge+1+m);
        num=n,root=0,cnt=0;
        for(int i=1;i<=2*n;i++)p[i]=i,h[i]=-1,w[i]=0;

        for(int i=1;i<=m;i++)
        {
                int x=find(edge[i].u),y=find(edge[i].v);
                if(x!=y)
                {
                        p[x]=p[y]=++num;
                        root=max(root,num);
                        w[num]=edge[i].val;
                        add(num,x),add(x,num);
                        add(num,y),add(y,num);
                }
        }
}


活动打卡代码 AcWing 2154. 梦幻布丁

Noe1017
22天前
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=1e6+10;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],idx,h[N];
int p[N],sz[N],col[N],ans;
void add(int a,int b)
{
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
        sz[a]++;
}
void merge(int &x,int &y)
{
        if(x==y)return ;

        if(sz[x]>sz[y])swap(x,y);

        for(int i=h[x];~i;i=ne[i])
        {
                int j=e[i];
                ans-=(col[j-1]==y)+(col[j+1]==y);
        }
        for(int i=h[x];~i;i=ne[i])
        {
                int j=e[i];
                col[j]=y;
                if(ne[i]==-1)
                {
                        ne[i]=h[y],h[y]=h[x];
                        break;
                }
        }
        h[x]=-1;
        sz[y]+=sz[x],sz[x]=0;
        return ;
}
void solve()
{
       int n,m;
       cin>>n>>m;
       memset(h,-1,sizeof h);
       for(int i=1;i<=n;i++)
       {
               cin>>col[i];
               add(col[i],i);
               ans+=(col[i]!=col[i-1]);
       }
       for(int i=0;i<M;i++)p[i]=i;

       while(m--)
       {
               int op;cin>>op;
               if(op==1)
               {
                   int x,y;cin>>x>>y;
                   merge(p[x],p[y]);    
               }else cout<<ans<<endl;
       }
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}



分享 ST表

Noe1017
1个月前

ST表

作为$LCA$的前置知识.解决各种简单的区间问题和$Dp$优化拥有十分重要的作用.

首先从暴力说起.

1273.天才的记忆

ST表的前身,为一个暴力的动态规划.
之所以很难直接看懂ST表,很大一部分原因是因为直接跳过了暴力来学习.

对于 1273 这题来说,
可以定义 $Dp[i][j]$:左端点为$i$,右端点为j这段区间的,区间最值.
(此处可以是最值,也可以是$gcd$或者$lcm$)只要满足$f(a,a)=a$即可

状态转移:$Dp[i][j]=max(Dp[i][j-1],a[j])$

对于该方程,由于转移的时候,只有第二维发生变化,因此 第一层循环枚举$i$,第二层循环枚举$j$

Code:

void init()
{
        for(int i=1;i<=n;i++)
         for(int j=i;j<=n;j++)
          if(i==j)st[i][j]=a[j];
          else st[i][j]=max(st[i][j-1],a[j]);
}

测试.jpg

显然暴力做法的时间复杂度以及空间复杂度均为:$O(n^2)$.

因此就引出了二进制优化.

为什么可以进行二进制优化呢?

先给出优化过后$ST$表的状态转移方程以及定义.

$ST[i][j]$:以$i$为左端点,长度为$2^j$的区间最大值.

状态转移 Code:

初始化

void init()
{
        for(int j=0;j<=(int)log2(n);j++)
         for(int i=1;i+(1<<j)-1<=n;i++)
          if(!j)st[i][j]=a[i];
          else st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

Explanation:

当$j$为$0$,此时区间长度为$1$.区间最值就是其本身对应的数组中的数.
当$j$不为$0$,此时就将区间分成两部分,对应于暴力的话:
左端就是从$[i,i+(1<<(j-1))-1)]$
右端就是从$[i+(1<<(j-1)),j]$

就相当于原来每次只是向右扩展了一小格.现在优化过后每次扩展为原来的一倍.

询问:

       while(m--)
       {
               int l,r;cin>>l>>r;
               int len=(int)log2(r-l+1);//dp len
            //   r-x+1=1<<len; 利用dp Len 求分块左端点 
               cout<<max(st[l][len],st[r-(1<<len)+1][len])<<endl;
       }

Explanation:

将查询区间的从长度取对数以后,才是我们状态定义的第二维.
由于len可能被下取整.因此我们就以利用$r-x+1=(1<<len)$.求出以$r$为右端点,长度为$len$的区间.

画图就是下面这样:画图.jpg

可以看到这样我们就完整的覆盖了查询区间.那么当$len$不被下取整的时候.左边和右边都会将整个区间给覆盖掉.

ST表 Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n;
int a[N];
int st[N][(int)log2(N)];
void init()
{
        for(int j=0;j<=(int)log2(n);j++)
         for(int i=1;i+(1<<j)-1<=n;i++)
          if(!j)st[i][j]=a[i];
          else st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
void solve()
{
       cin>>n;
       for(int i=1;i<=n;i++)cin>>a[i];
       init();//预处理st表 
       int m;cin>>m;
       while(m--)
       {
               int l,r;cin>>l>>r;
               int len=(int)log2(r-l+1);//dp len
            //   r-x+1=1<<len; 利用dp Len 求分块左端点 
               cout<<max(st[l][len],st[r-(1<<len)+1][len])<<endl;
       }
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
     //   freopen("test.in","r",stdin);
        solve();
        return 0;
}



Noe1017
1个月前

E. Number of Groups

思路:
经典的二维转换成一维问题.
首先需要将所有二维的线段看成一维的两个点.放入一个容器中进行处理.
在处理过程中,我们同时维护两种颜色的左端点集合.
由于对于已经开放的左端点但还没有终结的点而言,此时任意出现的右端点一定会和其相连接.
但是连接的过程是一个贪心的过程,即每次合并之后,对于当前点的另一个颜色的左端点集合而言,
除了最晚离开的那个,其余都可以被它给代表.因此进行一个删除操作,这样总体的时间复杂度,会随着
每一次合并之后及时将多余的点删除从而做到均摊$O(n)$

Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n;
struct DSU{
        vector<int>fa,s;
        int cnt;
        DSU(int n=1):fa(n+1,-1),s(n+1,1),cnt(n){}
        int find(int x){return fa[x]==-1?x:fa[x]=find(fa[x]);}
        int size(int x){return s[find(x)];}
        void merge(int x,int y)
        {
                x=find(x),y=find(y);
                if(x==y)return ;
                s[x]+=s[y];
                cnt--;
                fa[y]=x;
        }
};
struct point{
        int col,t,id,val;
        bool operator <(const point &a)const
        {
                return val<a.val;
        }
};
struct Seg{
        int col,l,r,id;
};
void solve()
{
      cin>>n;
      vector<point>a;
      vector<Seg>seg(n+1);
      for(int i=1;i<=n;i++)
      {
         int col,l,r;
         cin>>col>>l>>r;
         seg[i]={col,l,r,i};
         a.push_back({col,0,i,l});
         a.push_back({col,1,i,r});
      } 
      sort(a.begin(),a.end());
      vector<bool>vis(n+1,0);
      vector<vector<int>>s(2);
      vector<int>w;
      int last=-1;
      DSU dsu(n);
      for(auto c:a)
      {
              if(c.val!=last)
              {
                      for(auto x:w)vis[x]=true;
                      last=c.val;
                      w.clear();
              }
              if(!s[c.col^1].empty())
              {
                      int k=-1;
                      for(auto x:s[c.col^1])
                       if(!vis[x])
                       {
                               dsu.merge(x,c.id);
                               if(k==-1||seg[x].r>seg[k].r)k=x;
                       }
                      s[c.col^1].clear();
                      if(k!=-1)s[c.col^1].push_back(k);
              }
              if(c.t)w.push_back(c.id);
              else s[c.col].push_back(c.id);
      }
      cout<<dsu.cnt<<endl;
      return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}




分享 封装DSU

Noe1017
1个月前

由于经常需要使用到并查集的各种功能.
因此封装一下,使得整体代码更为简洁.

DSU Code:

int n,m;
struct DSU
{
        vector<int>fa,s;
        int cnt;//连通块数量.
        DSU(int n=1):fa(n+1,-1),s(n+1,1),cnt(n){}
        int size(int x){return s[find(x)];}
        int find(int x){return fa[x]==-1?x:fa[x]=find(fa[x]);}

        bool connect(int x,int y)
        {
                x=find(x),y=find(y);
                if(x==y)return true;
                else return false;
        }

        void merge(int x,int y)
        {
                x=find(x),y=find(y);
                if(x==y)return ;
                s[x]+=s[y];
                fa[y]=x;
        }
};

注意初始化:

 DSU dsu(n);//初始化



Noe1017
1个月前

H. Gambling

思路:
单独考虑每一种值的答案.
这就等价于,对于每一个值所构成的元素集合,求最大子段和.

状态表示:以第$i$个元素结尾的最大子段和.

状态转移方程为:$dp[i] = max(dp[i-1] + a[i],a[i])$

由于值会比较大因此,需要将所有的值离散化以后再进行合并.
每次用当前其对应集合中的最后一个元素和其转移即可.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
vector<int>nums;
vector<int>block[N];
int find(int x)
{
        return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
struct node{
        int val,l,r;
};
node dp[N];
void solve()
{
       int n;cin>>n;
       vector<int>a(n+1);
       for(int i=1;i<=n;i++)cin>>a[i],nums.push_back(a[i]);
       sort(nums.begin(),nums.end());
       nums.erase(unique(nums.begin(),nums.end()),nums.end());

       for(int i=0;i<=n;i++)dp[i].val=-inf,dp[i].l=dp[i].r=i;
       node ans={a[1],1,1};//初始化 
       int cur=1;
       for(int i=1;i<=n;i++)
       {
               int pos=find(a[i]);
               if(block[pos].size())
               {
                       int res=block[pos].back();
                       dp[i].val=max(1,dp[res].val+2-(i-(res+1)+1));
                       if(dp[i].val!=1)dp[i].l=dp[res].l;
                       if(dp[i].val>cur)ans={a[i],dp[i].l,dp[i].r},cur=dp[i].val;
               }else dp[i].val=1,dp[i].l=dp[i].r=i;
               block[pos].push_back(i);
       }
    //   cout<<dp[5].val<<endl;
       for(int i=1;i<=n;i++)
       {
               int pos=find(a[i]);
               if(block[pos].size())block[pos].clear();
       }
       cout<<ans.val<<' '<<ans.l<<' '<<ans.r<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
  //      freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)solve();
        return 0;
}