20180210讲课

2018-02-10 19:01:23 By youyl

字符串相关

NOIP中和字符串相关的通常只有输入输出部分

历年字符串相关题目:

  • NOIP2012Vigenère密码
  • NOIP2017时间复杂度
  • NOIP2016玩具谜题
  • NOIP2015子串

KMP

KMP学习:http://www.matrix67.com/blog/archives/115

NOI2014动物园:http://uoj.ac/problem/5

标程:

#include<cstdio>
#include<cstring>
using namespace std;
int nxt[1200000];
int T;
char str[1200000];
const long long mod=1000000007;
long long ans;
int S[1200000];
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",str+1);
        int ll=strlen(str+1);
        nxt[1]=0;
        S[1]=1;
        ans=1;
        int p1=0,p2=0;
        for (int i=2;i<=ll;i++)
        {
            while (p1!=0&&str[i]!=str[p1+1])
            {
                p1=nxt[p1];
            }
            if(str[i]==str[p1+1])p1++;
            nxt[i]=p1;
            S[i]=S[nxt[i]]+1;
            while (p2!=0&&str[i]!=str[p2+1])
            {
                p2=nxt[p2];
            }
            if(str[i]==str[p2+1])p2++;
            while (p2>i/2)p2=nxt[p2];
            ans*=(S[p2]+1);ans%=mod;
        }printf("%lld\n",ans);
    }
    return 0;
}

字符串hash

题目:http://acm.nflsoj.com/problem/33

题解:http://acm.nflsoj.com/blog/youyl/blog/41

标程:

#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=1000000007;
const long long mul=131;
char str[1200000];
inline int solve()
{
    int l=strlen(str+1);
    int lb=1,rb=l,cnt=0;
    long long hashl=0,hashr=0,mult=1;
    while (lb<rb)
    {
        hashr+=mult*(str[rb]-'a'+1)%mod;
        hashr%=mod;
        hashl*=mul;hashl%=mod;
        hashl+=(str[lb]-'a'+1);
        hashl%=mod;
        if(hashl==hashr)
        {
            hashl=0;
            hashr=0;
            mult=1;
            cnt+=2;
        }
        else
        {
            mult*=mul;
            mult%=mod;
        }
        lb++;
        rb--;
    }
    if(lb==rb)cnt++;
    if(lb!=rb&&hashl!=0)cnt++;
    return cnt;
}
int T;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",str+1);
        printf("%d\n",solve());
    }
    return 0;
}

头文件相关

使用规则:http://www.noi.cn/about/rules/362-noi

全面的内容:http://www.cplusplus.com/reference/

下午演示的一些函数和容器的用法还需要各位多加练习。

2018 Winter Series 7th 题解

2018-02-10 12:18:26 By youyl

题解

扑克牌

本题有很多做法,以下给出一种简单的做法:

先在首尾各加入一个0,然后考虑相邻两个数的差的绝对值。

首先每次去掉一个顺子必然是去掉尽可能长的顺子,即开头和结尾的值不为0。

每次去掉一个顺子只会在顺子的开头和结尾发生变化。

所以答案就是相邻两个数的差的绝对值的和除以2。

直径

考虑去掉一条边,树被分成了两个部分。

然后考虑这两个部分的直径,那么最大值显然是将两个部分的直径首尾相连,最小值显然是连接两个直径的中点。

只需要维护树上每条边两侧的两个子树的直径即可。

字符串

满足条件2的子串很好处理。

接下来考虑满足条件1的子串。

设前i个字符中,B的个数是b[i],S的个数是s[i],C的个数是c[i]。

那么考虑考虑一段j+1到i的子串,满足条件1的子串需要满足:

  • c[i]-c[j]!=s[i]-s[j]
  • c[i]-c[j]!=b[i]-b[j]
  • b[i]-b[j]!=s[i]-s[j]

移项可以得到:

  • c[i]-s[i]!=c[j]-s[j]
  • c[i]-b[i]!=c[j]-b[j]
  • b[i]-s[i]!=b[j]-s[j]

所以对每个点维护c[i]-s[i],c[i]-b[i],b[i]-s[i]

按照第一维排序,用树状数组维护第二维的前缀和后缀,树状数组中存储i的最大值,第三维不同的最大值,最小值,第三维不同的最小值

最终复杂度$O(n\log n)$

标程

扑克牌

#include<cstdio>
using namespace std;
long long a[120000];
int n;
long long ans;
inline long long fab(long long x)
{
    if(x>0)return x;
    return -x;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for (int i=1;i<=n+1;i++)
    {
        ans+=fab(a[i]-a[i-1]);
    }
    printf("%lld\n",ans/2);
    return 0;
}

直径

#include<cstdio>
#include<algorithm>
using namespace std;
int n,x1,x2;
int ed,st[520000];
struct node
{
    int to,next;
}g[1200000];
int minn,maxx;
inline void add(int x,int y)
{
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    st[x]=ed;
}
int fir[520000];
int sec[520000];
int thi[520000];
int dia[520000];
int fd[520000];
int sd[520000];
inline void dfs(int x,int fa)
{
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            dfs(g[i].to,x);
            thi[x]=max(thi[x],fir[g[i].to]+1);
            if(sec[x]<thi[x])
            {
                swap(sec[x],thi[x]);
            }
            if(sec[x]>fir[x])
            {
                swap(sec[x],fir[x]);
            }
            dia[x]=max(dia[x],dia[g[i].to]);
            sd[x]=max(sd[x],dia[g[i].to]);
            if(sd[x]>fd[x])swap(sd[x],fd[x]);
        }
    }
    dia[x]=max(dia[x],fir[x]+sec[x]);
}
inline int calc(int x,int y)
{
    return max(max(x,y),x/2+y/2+x%2+y%2+1);
}
inline void solve(int x,int fa,int dis,int lg)
{
    if(fa!=0)
    {
        minn=min(minn,calc(dis,dia[x]));
        maxx=max(maxx,dis+1+dia[x]);
    }
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            int tmp1=fir[x],tmp2=fd[x];
            if(tmp2==dia[g[i].to])
            {
                tmp2=sd[x];
            }
            if(tmp1==fir[g[i].to]+1)
            {
                tmp1=sec[x];
                tmp2=max(tmp2,sec[x]+max(thi[x],lg));
            }
            else if(sec[x]==fir[g[i].to]+1)
            {
                tmp2=max(tmp2,fir[x]+max(thi[x],lg));
            }
            else
            {
                tmp2=max(tmp2,fir[x]+max(sec[x],lg));
            }
            tmp1=max(lg,tmp1);
            tmp2=max(tmp2,dis);
            solve(g[i].to,x,tmp2,tmp1+1);
        }
    }
}
int main()
{
    scanf("%d",&n);
    minn=1000000000;
    for (int i=1;i<n;i++)
    {
        scanf("%d %d",&x1,&x2);
        add(x1,x2);
        add(x2,x1);
    }
    dfs(1,0);
    solve(1,0,0,0);
    printf("%d\n%d\n",minn,maxx);
    return 0;
}

字符串

#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans,top;
const int M=1000010;
char str[1200000];
int b[1200000];
int c[1200000];
int s[1200000];
struct node
{
    int b,c;
}a[1200000];
int ed,st[2200000];
struct graph
{
    int to,next;
}g[1200000];
inline int lowbit(int x)
{
    return (x&(-x));
}
inline void add(int x,int y)
{
    ed++;
    g[ed].to=y;
    g[ed].next=st[x];
    st[x]=ed;
}
struct nodeminmax
{
    int mi1,mi2,mx1,mx2;
    nodeminmax()
    {
        mi1=-1;
        mi2=-1;
        mx1=-1;
        mx2=-1;
    }
    inline void update(int pos)
    {
        if(mi1==-1)
        {
            mx1=pos;
            mi1=pos;
            return;
        }
        if(mi1>pos)
        {
            if(a[pos].c!=a[mi1].c)
            {
                mi2=mi1;
            }
            mi1=pos;
        }
        else if((mi2==-1||mi2>pos)&&(a[pos].c!=a[mi1].c))
        {
            mi2=pos;
        }
        if(mx1<pos)
        {
            if(a[pos].c!=a[mx1].c)
            {
                mx2=mx1;
            }
            mx1=pos;
        }
        else if((mx2==-1||mx2<pos)&&(a[pos].c!=a[mx1].c))
        {
            mx2=pos;
        }
    }
    inline void query(int pos)
    {
        if(mx1!=-1&&a[pos].c!=a[mx1].c)
        {
            ans=max(ans,mx1-pos);
        }
        else if(mx2!=-1&&a[pos].c!=a[mx2].c)
        {
            ans=max(ans,mx2-pos);
        }
        if(mi1!=-1&&a[pos].c!=a[mi1].c)
        {
            ans=max(ans,pos-mi1);
        }
        else if(mi2!=-1&&a[pos].c!=a[mi2].c)
        {
            ans=max(ans,pos-mi2);
        }
    }
};
struct prebit
{
    nodeminmax a[2200000];
    inline void update(int b,int pos)
    {
        while (b<=top)
        {
            a[b].update(pos);
            b+=lowbit(b);
        }
    }
    inline void query(int b,int pos)
    {
        while (b)
        {
            a[b].query(pos);
            b-=lowbit(b);
        }
    }
}pre;
struct sufbit
{
    nodeminmax a[2200000];
    inline void update(int b,int pos)
    {
        while (b)
        {
            a[b].update(pos);
            b-=lowbit(b);
        }
    }
    inline void query(int b,int pos)
    {
        while (b<=top)
        {
            a[b].query(pos);
            b+=lowbit(b);
        }
    }
}suf;
int main()
{
    ans=0;
    int bef=0;
    scanf("%d",&n);
    scanf("%s",str+1);
    for (int i=1;i<=n;i++)
    {
        if(i==n||str[i]!=str[i+1])
        {
            ans=max(i-bef,ans);
            bef=i;
        }
    }
    a[0].b=0;
    a[0].c=0;
    add(M,0);
    for (int i=1;i<=n;i++)
    {
        b[i]=b[i-1]+(str[i]=='B');
        c[i]=c[i-1]+(str[i]=='C');
        s[i]=s[i-1]+(str[i]=='S');
        a[i].b=c[i]-s[i];
        a[i].c=s[i]-b[i];
        add(b[i]-c[i]+M,i);
    }
    top=M+M+10;
    for (int x=1;x<=top;x++)
    {
        for (int i=st[x];i!=0;i=g[i].next)
        {
            pre.query(a[g[i].to].b+M-1,g[i].to);
            suf.query(a[g[i].to].b+M+1,g[i].to);
        }
        for (int i=st[x];i!=0;i=g[i].next)
        {
            pre.update(a[g[i].to].b+M,g[i].to);
            suf.update(a[g[i].to].b+M,g[i].to);
        }
    }
    printf("%d\n",ans);
    return 0;
}

20180206 题目列表

2018-02-06 15:48:01 By youyl

NOIP2014 联合权值

https://www.luogu.org/problemnew/show/P1351

考虑距离为2的点对的时候考虑他们的中点

第一问很容易解决,在每个点上记录相邻点的最大值和次大值即可

第二问可以按照每条边分别计算对答案的贡献

NOIP2013 货车运输

https://www.luogu.org/problemnew/show/P1967

首先找出最大生成树

然后问题变成询问树上一条路径的最小值

用树上倍增解决

NOIP2015 运输计划

https://www.luogu.org/problemnew/show/P2680

先二分答案,假设二分的答案是t

长度小于等于t的路径可以直接排除,接下来就是在剩余路径的交集中找一条权值最大的路径进行改造

使用树上差分可以快速求出交集

NOIP2012 疫情控制

https://www.luogu.org/problemnew/show/P1084

先二分答案

可以看出让所有的军队尽量向上走一定是最优的。可以倍增求出所有的军队在mid的时间里最多走到哪个点。

对于所有走不到根的军队,它们就只能停在那里了。对于所有走到根之后还有剩余时间的军队,可以继续走到根的别的儿子上,这些军队成为可以调动的军队。

枚举根的每一个儿子,如果这个儿子所代表的子树已经被控制了,即子树中所有走不到根的军队已经可以控制了这个子树,就不用管它。

如果它代表的子树没有被控制(注意这里不包括经过这个子树走到根的点),那么称这个点为需要调入的点。

所有可调动的军队都有一个剩余时间,所有需要调入的点都有一个需要时间(即根到儿子的边的权),将这两种点分别从小到大排序,贪心地分配,就可以达到目的。

需要注意的一点是,所有能走到根的军队一定是从根的某一个儿子走上来的,如果再让这个军队调去这个儿子的话,不能计算时间。具体做法是从小到大排序后,如果当前军队走上来的那个点没有被控制的话,就让这支军队去控制它走上来的那个点,否则的话,让它去控制它能控制的最小的点。

NOIP2016 天天爱跑步

https://www.luogu.org/problemnew/show/P1600

将每条路径按照lca拆成两条链,考虑自下而上的那条链,设它为u->v

设di为点i的深度,那么路径上的点必须满足du-di=wi,即di+wi=du才可以收到u->v的贡献,问题转化成支持以下两种操作:1.给一条路径上每个点加入一个数x 2.查询一个点上有多少个di+wi

先用差分转化一下,将操作1改为在u处插入一个数x,在v的父亲处删除一个数x,那么操作2就变成了子树询问

通过dfs序将子树操作转化为序列操作,这时候可以使用可持久化数据结构来实现

如果不使用可持久化数据结构,就考虑离线,先把所有操作预处理出来,按照dfs序顺推,每到一个点就计算该点对应的询问

自上而下的那条链可以用类似方法处理

bzoj1787 紧急集合

http://www.lydsy.com/JudgeOnline/problem.php?id=1787

求出三个点两两lca,其中有两个相同,答案为另一个

codeforces 519E

http://codeforces.com/problemset/problem/519/E

设询问的点为A和B,分四种情况讨论

  • A=B:答案为n

  • A和B距离为奇数:答案为0

  • A和B到他们最近公共祖先P的距离相等:则答案为n减去A和B对应的P的儿子的子树大小

  • 其他情况:假设A的深度更大,找到A和B的中点M,答案为M的子树大小减去A对应的M的儿子的子树大小

货车运输标程

2018-02-06 13:48:32 By youyl
#include<cstdio>
#include<algorithm>
using namespace std;
struct edge
{
    int fir,sec,dis;
}edg[200000];
inline bool cmp(edge x,edge y)
{
    return x.dis>y.dis;
}
struct node
{
    int to,next,dis;
}g[220000];
int ed,st[120000];
int fat[120000];
inline int fnd(int x)
{
    if(fat[x]==x)return x;
    return fat[x]=fnd(fat[x]);
}
inline void add(int x,int y,int z)
{
    ed++;
    g[ed].next=st[x];
    g[ed].to=y;
    g[ed].dis=z;
    st[x]=ed;
}
int n,m,q,x1,x2,vis[120000];
int par[120000][20];
int val[120000][20],dep[120000];
const int inf=(int)1e8;
inline void dfs(int x,int fa,int de)
{
    vis[x]=1;
    dep[x]=de;
    par[x][0]=fa;
    for (int i=st[x];i!=0;i=g[i].next)
    {
        if(g[i].to!=fa)
        {
            val[g[i].to][0]=g[i].dis;
            dfs(g[i].to,x,de+1);
        }
    }
}
inline void doubling()
{
    for (int i=0;i<=18;i++)
    {
        val[0][i]=inf;
    }
    for (int i=1;i<=18;i++)
    {
        for (int j=1;j<=n;j++)
        {
            par[j][i]=par[par[j][i-1]][i-1];
            val[j][i]=min(val[j][i-1],val[par[j][i-1]][i-1]);
        }
    }
}
inline int query(int x,int y)
{
    int ans=inf;
    if(dep[x]>dep[y])swap(x,y);
    for (int i=18;i>=0;i--)
    {
        if(dep[par[y][i]]>=dep[x])
        {
            ans=min(ans,val[y][i]);
            y=par[y][i];
        }
    }
    if(x==y)
    {
        return ans;
    }
    for (int i=18;i>=0;i--)
    {
        if(par[x][i]!=par[y][i])
        {
            ans=min(ans,val[x][i]);
            ans=min(ans,val[y][i]);
            x=par[x][i];
            y=par[y][i];
        }
    }
    if(x==y)return ans;
    ans=min(ans,val[x][0]);
    ans=min(ans,val[y][0]);
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&edg[i].fir,&edg[i].sec,&edg[i].dis);
    }
    sort(edg+1,edg+m+1,cmp);
    for (int i=1;i<=n;i++)
    {
        fat[i]=i;
    }
    for (int i=1;i<=m;i++)
    {
        if(fnd(edg[i].fir)!=fnd(edg[i].sec))
        {
            add(edg[i].fir,edg[i].sec,edg[i].dis);
            add(edg[i].sec,edg[i].fir,edg[i].dis);
            fat[fnd(edg[i].fir)]=fnd(edg[i].sec);
        }
    }
    for (int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            val[i][0]=inf;
            dfs(i,0,1);
        }
    }
    doubling();
    scanf("%d",&q);
    while (q--)
    {
        scanf("%d %d",&x1,&x2);
        if(fnd(x1)!=fnd(x2))
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",query(x1,x2));
        }
    }
    return 0;
}

2018 Winter Series 3rd 题解和标程

2018-02-06 12:19:28 By youyl

题解

印章

题意:用一个网格图形去覆盖另一个网格图图形并且不能旋转,重叠和溢出

考虑到方格纸最左上角的黑点和印章最左上角的墨水必然是重合的

将印章里的墨水点存在一个链表里,直接暴力依次覆盖方格纸上的黑点,并把覆盖过的黑点清空

复杂度是$O(nm)$

膜法师

题意:给出一个序列,有些节点是特殊的但是你不知道,每次你可以花费一定代价询问一段连续的区间中特殊点数量的奇偶性,问能够必然确定特殊点的最小花费。

考虑相邻两个数之间的缝隙。(包括第一个数之前和最后一个数之后)

每个询问都是在询问两个缝隙之间的奇偶性。

实际上题目要求的就是你最后必须能推导出每个数前后缝隙之间的奇偶性。

考虑将每个缝隙看作是一个点,询问就是在两个点之间建边,如果两个缝隙对应的点相邻,那么他们之间的奇偶性就可以得到。

所以问题转化成了最小生成树,边权就是对应的询问花费

看电影

题意:给出一个序列,每个节点有一种颜色,每种颜色有对应的权值,要求找出一个区间,使得区间内只出现过一次的颜色的权值之和最大。

先预处理出对于每个节点,下一个跟他相同颜色的点的位置,定义它为$nxt[i]$

然后枚举最后选的那个区间的左端点$L$,用一颗线段树记录对于每个$R$,这个区间的得分是多少

当左端点$L$向右移时,设当前左端点颜色为$i$,相当于把以$L$到$nxt[L]-1$为结尾的区间的得分减$w[i]$,再把以$nxt[L]$到$nxt[nxt[L]]-1$为结尾的区间的得分加$w[i]$

然后查询以$L$到$n$为结尾的区间的得分的最大值,得到$L$为开头的所有区间的得分的最大值

复杂度为$O(n\log n)$

标程

印章

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<pair<int,int> >adj;
int n,m,a,b,T;
bool mp[1200][1200];
char str[1200];
inline bool solve(int x,int y)
{
    if(adj.size()==0)return true;
    int sx=x-adj[0].first,sy=y-adj[0].second;
    for (int i=0;i<adj.size();i++)
    {
        int tx=sx+adj[i].first;
        int ty=sy+adj[i].second;
        if(tx<1||tx>n||ty<1||ty>m)return true;
        if(!mp[tx][ty])return true;
        mp[tx][ty]=false;
    }
    return false;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(mp,0,sizeof(mp));
        adj.clear();
        scanf("%d %d %d %d",&n,&m,&a,&b);
        for (int i=1;i<=n;i++)
        {
            scanf("%s",str+1);
            for (int j=1;j<=m;j++)
            {
                if(str[j]=='x')mp[i][j]=true;
            }
        }
        for (int i=1;i<=a;i++)
        {
            scanf("%s",str+1);
            for (int j=1;j<=b;j++)
            {
                if(str[j]=='x')adj.push_back(make_pair(i,j));
            }
        }
        int fl=0;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                if(mp[i][j])
                {
                    if(solve(i,j))
                    {
                        printf("NIE\n");
                        fl=1;break;
                    }
                }
            }
            if(fl==1)break;
        }if(fl==0)printf("TAK\n");
    }
    return 0;
}

膜法师

#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
int cnt,x1,x2;
pair<int,pair<int,int> >edge[2200000];
int fat[2010];
inline int fnd(int x)
{
    if(fat[x]==x)return x;
    return fat[x]=fnd(fat[x]);
}
int n,cnt2;
long long ans;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        fat[i]=i;
        for (int j=i;j<=n;j++)
        {
            scanf("%d",&x1);
            cnt++;
            edge[cnt]=make_pair(x1,make_pair(i,j+1));
        }
    }
    fat[n+1]=n+1;
    sort(edge+1,edge+cnt+1);
    for (int i=1;i<=cnt;i++)
    {
        x1=edge[i].second.first;
        x2=edge[i].second.second;
        if(fnd(x1)!=fnd(x2))
        {
            fat[fnd(x1)]=fnd(x2);
            cnt2++;
            ans+=edge[i].first;
            if(cnt2==n)break;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

看电影

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int f[1200000];
int w[1200000];
int next[1200000];
int las[1200000];
struct segment
{
    int lef[5200000];
    int rig[5200000];
    long long val[5200000];
    long long laz[5200000];
    inline void update(int x)
    {
        val[x]=max(val[x*2],val[x*2+1]);
    }
    inline void upgrade(int x,long long va)
    {
        laz[x]+=va;
        val[x]+=va;
    }
    inline void pushdown(int x)
    {
        upgrade(x*2,laz[x]);
        upgrade(x*2+1,laz[x]);
        laz[x]=0;
    }
    inline void build(int x,int le,int ri)
    {
        lef[x]=le;
        rig[x]=ri;
        val[x]=0;
        laz[x]=0;
        if(le==ri)return;
        build(x*2,le,(le+ri)/2);
        build(x*2+1,(le+ri)/2+1,ri);
    }
    inline void edit(int x,int le,int ri,long long va)
    {
        if(le>ri)return;
        if(le<=lef[x]&&ri>=rig[x])
        {
            upgrade(x,va);
            return;
        }
        pushdown(x);
        if(le<=rig[x*2])edit(x*2,le,ri,va);
        if(ri>rig[x*2])edit(x*2+1,le,ri,va);
        update(x);
    }
    inline long long query(int x,int le,int ri)
    {
        if(le>ri)return 0;
        if(le<=lef[x]&&ri>=rig[x])
        {
            return val[x];
        }
        long long summ=0;
        if(le<=rig[x*2])summ=max(summ,query(x*2,le,ri));
        if(ri>rig[x*2])summ=max(summ,query(x*2+1,le,ri));
        return summ;
    }
}sgt;
long long ans;
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&w[i]);
        las[i]=n+1;
    }
    for (int i=n;i>=1;i--)
    {
        next[i]=las[f[i]];
        las[f[i]]=i;
    }
    sgt.build(1,1,n);
    for (int i=1;i<=m;i++)
    {
        if(las[i]!=n+1)
        {
            sgt.edit(1,las[i],next[las[i]]-1,w[i]);
        }
    }
    for (int i=1;i<=n;i++)
    {
        ans=max(ans,sgt.query(1,i,n));
    //    printf("%d %lld\n",i,ans);
        if(next[i]!=n+1)
        {
            sgt.edit(1,i,next[i]-1,-w[f[i]]);
            sgt.edit(1,next[i],next[next[i]]-1,w[f[i]]);
        }
        else
        {
            sgt.edit(1,i,n,-w[f[i]]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}
youyl Avatar