题目背景
影魔，奈文摩尔，据说有着一个诗人的灵魂。 事实上，他吞噬的诗人灵魂早已成千上万。
千百年来，他收集了各式各样的灵魂，包括诗人、 牧师、 帝王、 乞丐、 奴隶、 罪人，当然，还有英雄。
题目描述
每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。
奈文摩尔有 n 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 1 到 n。第 i个灵魂的战斗力为 k[i]，灵魂们以点对的形式为影魔提供攻击力，对于灵魂对 i， j(i<j)来说，若不存在 ks大 于 k[i]或者 k[j]，则会为影魔提供 p1 的攻击力（可理解为： 当 j=i+1 时，因为不存在满足 i<s<j 的 s，从而 k[s]不存在，这时提供 p1 的攻击力；当 j>i+1 时，若max{k[s]|i<s<j}<=min{k[i],k[j]} ， 则 提 供 p1 的 攻 击 力 ）； 另 一 种 情 况 ， 令 c 为k[i+1],k[i+2],k[i+3]……k[j-1]的最大值，若 c 满足： k[i]<c<k[j],或者 k[j]<c<k[i]，则会为影魔提供 p2 的攻击力，当这样的 c 不存在时，自然不会提供这 p2 的攻击力；其他情况的点对，均不会为影魔提供攻击力。
影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间[a,b]， 1<=a<b<=n，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑 所有满足a<=i<j<=b 的灵魂对 i,j 提供的攻击力之和。
顺带一提，灵魂的战斗力组成一个 1 到 n 的排列： k[1],k[2],…,k[n]。
输入输出格式
输入格式：
输入文件名为 sf.in。
第一行 n,m,p1,p2
第二行 n 个数： k[1],k[2],…,k[n]
接下来 m 行， 每行两个数 a,b， 表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。
输出格式：
输出文件名为 sf.out
共输出 m 行，每行一个答案，依次对应 m 个询问。
输入输出样例
10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
30
39
4
13
16
说明
30%： 1<= n,m <= 500。
另 30%: p1=2*p2。
100%:1 <= n,m <= 200000； 1 <= p1,p2 <= 1000。
补上一个更好理解的方法：主席树
令L[i]为i前第一个比a[i]大的一位，R[i]为i后第一个比a[i]大的一位
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long lol;
struct ZYYS
{
int c,p,l,r;
}q[];
int pos,ch[][],root[],a[],sta[],top,n,m,lst[],nxt[],cnt;
lol sum[],lazy[],p1,p2;
bool cmp(ZYYS a,ZYYS b)
{
return a.p<b.p;
}
void update(int &rt,int l,int r,int L,int R,lol k,int last)
{
int x=rt;
if (rt<=last)
{
rt=++pos;
ch[rt][]=ch[x][];ch[rt][]=ch[x][];
sum[rt]=sum[x];
lazy[rt]=lazy[x];
}
if (l>=L&&r<=R)
{
sum[rt]+=(r-l+)*k;
lazy[rt]+=k;
return ;
}
int mid=(l+r)/;
if (L<=mid) update(ch[rt][],l,mid,L,R,k,last);
if (R>mid) update(ch[rt][],mid+,r,L,R,k,last);
sum[rt]=sum[ch[rt][]]+sum[ch[rt][]]+(r-l+)*lazy[rt];
}
lol query(int x,int y,int l,int r,int L,int R,lol la)
{
if (l>=L&&r<=R)
{
return sum[y]-sum[x]+la*(r-l+);
}
int mid=(l+r)/;
lol s=;
if (L<=mid) s+=query(ch[x][],ch[y][],l,mid,L,R,la+lazy[y]-lazy[x]);
if (R>mid) s+=query(ch[x][],ch[y][],mid+,r,L,R,la+lazy[y]-lazy[x]);
return s;
}
int main()
{int i,x,l,r,last=;
cin>>n>>m>>p1>>p2;
for (i=;i<=n;i++)
scanf("%d",&a[i]);
top=;
for (i=;i<=n;i++)
{
while (top&&a[sta[top]]<a[i]) top--;
lst[i]=sta[top];
top++;
sta[top]=i;
}
top=;
sta[]=n+;
for (i=n;i>=;i--)
{
while (top&&a[sta[top]]<a[i]) top--;
nxt[i]=sta[top];
top++;
sta[top]=i;
}
for (i=;i<=n;i++)
{
if (lst[i]&&nxt[i]<=n)
{
q[++cnt]=(ZYYS){,lst[i],nxt[i],nxt[i]};
q[++cnt]=(ZYYS){,nxt[i],lst[i],lst[i]};
}
if (lst[i]&&nxt[i]-i>)
q[++cnt]=(ZYYS){,lst[i],i+,nxt[i]-};
if (nxt[i]<=n&&i-lst[i]>)
q[++cnt]=(ZYYS){,nxt[i],lst[i]+,i-};
}
sort(q+,q+cnt+,cmp);
x=;
last=;
for (i=;i<=cnt;i++)
{
while (x<q[i].p) root[x+]=root[x],x++,last=pos;
if (q[i].c==)
update(root[x],,n,q[i].l,q[i].r,p1,last);
else update(root[x],,n,q[i].l,q[i].r,*p2,last);
}
while (x<n) root[x+]=root[x],x++;
for (i=;i<=m;i++)
{
scanf("%d%d",&l,&r);
printf("%lld\n",query(root[l-],root[r],,n,l,r,)/+(r-l)*p1);
}
}
线段树：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Ask
{
int l,r,id;
}q[];
int a[],aa[],n,m,stack[],R[];
long long c[],mark[],ans[],p1,p2;
bool cmp(Ask a,Ask b)
{
return a.l<b.l;
}
void pushup(int rt)
{
c[rt]=c[rt*]+c[rt*+];
}
void pushdown(int rt,int l,int r,int mid)
{
if (mark[rt])
{
mark[rt*]+=mark[rt];
mark[rt*+]+=mark[rt];
c[rt*]+=mark[rt]*(mid-l+);
c[rt*+]+=mark[rt]*(r-mid);
mark[rt]=;
}
}
void change(int rt,int l,int r,int L,int R,long long d)
{
if (l>=L&&r<=R)
{
mark[rt]+=d;
c[rt]+=(r-l+)*d;
return;
}
pushdown(rt,l,r,(l+r)/);
int mid=(l+r)/;
if (L<=mid) change(rt*,l,mid,L,R,d);
if (R>mid) change(rt*+,mid+,r,L,R,d);
pushup(rt);
}
long long getsum(int rt,int l,int r,int L,int R)
{
if (l>=L&&r<=R)
{
return c[rt];
}
int mid=(l+r)/;
pushdown(rt,l,r,mid);
long long s=;
if (L<=mid) s+=getsum(rt*,l,mid,L,R);
if (R>mid) s+=getsum(rt*+,mid+,r,L,R);
pushup(rt);
return s;
}
void work()
{int i;
memset(c,,sizeof(c));
memset(mark,,sizeof(mark));
sort(q+,q+m+,cmp);
int top=;
stack[]=n+;
for (i=n;i>=;i--)
{
while (top&&a[i]>=a[stack[top]]) top--;
R[i]=stack[top];
stack[++top]=i;
}
top=m;
for (i=n;i>=;i--)
{
if (i+<=R[i]-)
change(,,n,i+,R[i]-,p2);
change(,,n,R[i],R[i],p1-p2);
while (top&&q[top].l==i)
ans[q[top].id]+=getsum(,,n,,q[top].r),top--;
}
}
void rev()
{int i;
for (i=;i<=n;i++)
aa[i]=a[n-i+];
for (i=;i<=n;i++)
a[i]=aa[i];
}
int main()
{int i;
cin>>n>>m>>p1>>p2;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
for (i=;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
work();
rev();
for (i=;i<=m;i++)
q[i].l=n+-q[i].l,q[i].r=n+-q[i].r,swap(q[i].l,q[i].r);
work();
for (i=;i<=m;i++)
printf("%lld\n",ans[i]);
}
庆祝FGO第一/二个SSR