[HNOI2017]影魔

C++14(g++5.4) 解法, 执行用时: 176ms, 内存消耗: 23784K, 提交时间: 2019-10-29 22:06:44

// luogu-judger-enable-o2
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Query { int x,l,r,id,v; };
struct Line { int x,l,r,v; };
bool operator <(Query a,Query b) { return a.x<b.x; }
bool operator <(Line a,Line b) { return a.x<b.x; }

int n,m,p1,p2;
int a[N],L[N],R[N];
int sta[N],top=0;
Query q[N<<1];
Line s[N*3];
ll c1[N],c2[N],ans[N];

inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) {
    if (!x) return;
    for (re int i=x;i<=n;i+=lowbit(i)) c1[i]+=y,c2[i]+=1ll*x*y;
}
inline ll sum(int x) {
    ll ans=0;
    for (re int i=x;i;i-=lowbit(i)) ans+=(x+1)*c1[i]-c2[i];
    return ans;
}

int main() {
    n=read(),m=read(),p1=read(),p2=read();
    for (re int i=1;i<=n;++i) a[i]=read();

    for (re int i=1;i<=n;++i) {
        while (top&&a[sta[top]]<a[i]) --top;
        L[i]=sta[top],sta[++top]=i;
    }
    sta[top=0]=n+1;
    for (re int i=n;i>=1;--i) {
        while (top&&a[sta[top]]<a[i]) --top;
        R[i]=sta[top],sta[++top]=i;
    }
    
    for (re int i=1;i<=m;++i) {
        int x=read(),y=read(); ans[i]+=(y-x)*p1;
        q[i]=(Query){x-1,x,y,i,-1};
        q[i+m]=(Query){y,x,y,i,1};
    }
    sort(q+1,q+m+m+1);
    
    int tot=0;
    for (re int i=1;i<=n;++i) {
        if (1<=L[i]&&R[i]<=n) s[++tot]=(Line){R[i],L[i],L[i],p1};
        if (1<=L[i]&&R[i]>i+1) s[++tot]=(Line){L[i],i+1,R[i]-1,p2};
        if (L[i]<i-1&&R[i]<=n) s[++tot]=(Line){R[i],L[i]+1,i-1,p2};
    }
    sort(s+1,s+tot+1);

    int pos1=1,pos2=1; while (!q[pos1].x) ++pos1;
    for (re int i=1;pos1<=m+m&&i<=n;++i) {
        while (pos2<=tot&&s[pos2].x<=i) {
            add(s[pos2].r+1,-s[pos2].v);
            add(s[pos2].l,s[pos2].v);
            ++pos2;
        }
        while (pos1<=m+m&&q[pos1].x<=i) {
            ans[q[pos1].id]+=q[pos1].v*(sum(q[pos1].r)-sum(q[pos1].l-1));
            ++pos1;
        }
    }
    for (re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}

C++(clang++11) 解法, 执行用时: 188ms, 内存消耗: 23544K, 提交时间: 2021-01-14 17:03:33

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define MAX 222222
inline int read()
{
    int x=0,t=1; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int L[MAX],R[MAX];
int a[MAX],n,m,p1,p2;
int S[MAX],top,cnt,tot;
struct Line{int x,l,r,v;}p[MAX<<2];
bool operator<(Line a,Line b){return a.x<b.x;}
struct query{int x,l,r,v,id;}q[MAX<<2];
bool operator<(query a,query b){return a.x<b.x;}
ll c1[MAX],c2[MAX],ans[MAX];
void Modify(int x,int w)
{
	for(int i=x;i<=n;i+=i&(-i))
		c1[i]+=w,c2[i]+=x*w;
}
ll Query(int x)
{
	ll ret=0;
	for(int i=x;i;i-=i&(-i))
		ret+=(x+1)*c1[i]-c2[i];
	return ret;
}
int main()
{
	n=read();m=read();p1=read();p2=read();
	for(int i=1;i<=n;++i)a[i]=read();
	S[top=0]=0;
	for(int i=1;i<=n;++i)
	{
		while(top&&a[S[top]]<a[i])--top;
		L[i]=S[top];S[++top]=i;
	}
	S[top=0]=n+1;
	for(int i=n;i>=1;--i)
	{
		while(top&&a[S[top]]<a[i])--top;
		R[i]=S[top];S[++top]=i;
	}
	for(int i=1;i<=m;++i)
	{
		int l=read(),r=read();ans[i]=(r-l)*p1;
		q[++cnt]=(query){r,l,r,1,i};
		q[++cnt]=(query){l-1,l,r,-1,i};
	}
	sort(&q[1],&q[cnt+1]);
	for(int i=1;i<=n;++i)
	{
		if(L[i]&&R[i]<n+1)p[++tot]=(Line){R[i],L[i],L[i],p1};
		if(L[i]&&R[i]>i+1)p[++tot]=(Line){L[i],i+1,R[i]-1,p2};
		if(L[i]+1<i&&R[i]<n+1)p[++tot]=(Line){R[i],L[i]+1,i-1,p2};
	}
	sort(&p[1],&p[tot+1]);
	for(int i=1,j=1;i<=cnt;++i)
	{
		while(j<=tot&&p[j].x<=q[i].x)
		{
			Modify(p[j].l,p[j].v);
			Modify(p[j].r+1,-p[j].v);
			++j;
		}
		ans[q[i].id]+=q[i].v*(Query(q[i].r)-Query(q[i].l-1));
	}
	for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
	return 0;
}

详情