洛谷3246 [hnoi2016]序列

HNOI套路题/数据结构题

Posted by yjjr's blog on February 27, 2018

题目

输入输出样例

输入样例#1

5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5


输出样例#1

28
17
11
11
17


说明

 1 <=N,Q <= 100000, Ai <= 10^9

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+7;
int n,m,a[maxn],Stack[maxn],top=0,le[maxn],ri[maxn],ep=0,p=0;
ll ans[maxn],ks[2][maxn],bs[2][maxn];
void modify(ll*f1,ll*f2,int x,ll f){
if(!x)return;
for(int w=x;w;w-=w&-w)f1[w]+=f;f*=x;
for(int w=x;w<=n;w+=w&-w)f2[w]+=f;
}
inline ll query(ll*f1,ll*f2,int x){
if(!x)return 0;ll re=0;
for(int w=x;w<=n;w+=w&-w)re+=f1[w];re*=x;
for(int w=x-1;w;w-=w&-w)re+=f2[w];
return re;
}
int l,r,id;
void run(){ans[id]=query(ks[0],ks[1],r)*l+query(bs[0],bs[1],r);}
}qs[maxn];
struct node{
int l,r1,r2;ll k,b;
void run(){
modify(ks[0],ks[1],r2,k),modify(ks[0],ks[1],r1-1,-k);
modify(bs[0],bs[1],r2,b),modify(bs[0],bs[1],r1-1,-b);
}
}sq[maxn<<1];
inline bool operator < (node a,node b){return a.l>b.l;}
int main(){
rep(i,1,n){
while(top&&a[Stack[top]]>a[i])ri[Stack[top--]]=i-1;
Stack[++top]=i;
}
while(top)ri[Stack[top--]]=n;
dep(i,n,1){
while(top&&a[Stack[top]]>=a[i])le[Stack[top--]]=i+1;
Stack[++top]=i;
}
while(top)le[Stack[top--]]=1;
rep(i,1,n){
sq[ep++]=(node){i+1,i,ri[i],-a[i],1LL*(i+1)*a[i]};
sq[ep++]=(node){le[i],i,ri[i],a[i],1LL*(-le[i])*a[i]};
}
sort(sq,sq+ep);