Description

　　给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：al,al+1,…,ar-
1,ar。若1≤l≤s≤t≤r≤n，则称a[s:t]是a[l:r]的子序列。现在有q个询问，每个询问给定两个数l和r，1≤l≤r
≤n，求a[l:r]的不同子序列的最小值之和。例如，给定序列5,2,4,1,3，询问给定的两个数为1和3，那么a[1:3]有
6个子序列a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]，这6个子序列的最小值之和为5+2+4+2+2+2=17。

Input

　　输入文件的第一行包含两个整数n和q，分别代表序列长度和询问数。接下来一行，包含n个整数，以空格隔开
,第i个整数为ai，即序列第i个元素的值。接下来q行，每行包含两个整数l和r，代表一次询问。

Output

　　对于每次询问，输出一行，代表询问的答案。

Sample Input

5 5

5 2 4 1 3

1 5

1 3

2 4

3 5

2 5
Sample Output

题解

一开始还看错题了。。
弄了一上午QAQ
然后去看了下题解，才发现理解错了。。
于是趁没看懂赶紧溜了回来。。

于是我们考虑莫队吧。。（唯一看懂的东西就是莫队
然后我们处理两个东西，L和R，表示这个点能影响的范围，也就是比他小的范围
然后对于新增加的一个点，我们可以跳他的L，R来找答案，直到找出范围为止
大概的处理过程是这样的：

LL Ri (LL l,LL r)
{LL x=r,re=0;while (x>=l){LL t=L[x];if (t<l) t=l;re=re+a[x]*(x-t+1);x=t-1;}
 return re;
}
LL Li (LL l,LL r)
{LL x=l,re=0;while (x<=r){LL t=R[x];if (t>r) t=r;re=re+a[x]*(t-x+1);x=t+1;}
 return re;
}
void solve ()
{LL l=1,r=1;LL ans=a[1];for (LL u=1;u<=q;u++){while (r<s[u].r) ans=ans+Ri(l,++r);while (l<s[u].l) ans=ans-Li(l++,r);while (l>s[u].l) ans=ans+Li(--l,r);while (r>s[u].r) ans=ans-Ri(l,r--);Ans[s[u].id]=ans;}for (LL u=1;u<=q;u++) printf("%lld\n",Ans[u]);
}

然而数据很水，居然20S刚好跑过去了
但是这个做法，即使是随机数据，也是O $(n \sqrt{n} \ log{n})$ 的
所以这个肯定是不行的

于是去认真地膜了一下题解。。
学会了st表的正确姿势

预处理出两个类似前缀和的数组sl[i]和sr[i]
其中sl[i]=sl[l[i]]+(i-l[i])*a[i]，sr同理
表示以这个为结束的答案的前缀和
左端点在l[i]及以前的答案就是sl[l[i]]，左端点在[l[i],i]之间的最小值肯定是a[i]，所以答案加上(i-l[i])*a[i]
嗯，挺好的。。
就这样吧。。

CODE:

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
typedef long long LL;
const LL N=100005;
LL n,q,nn;
LL a[N];
struct qq{LL l,r,id;}s[N];
LL ans[N];
LL belong[N];
bool cmp (qq a,qq b){
   return belong[a.l]==belong[b.l]?a.r<b.r:belong[a.l]<belong[b.l];}
LL L[N],R[N];//左边第一个比他小的数 右边第一个比他小的数 
stack<LL> sta;
LL sl[N],sr[N];
LL lg[N];
LL st[N][20];
LL pw[20];
LL getmin (LL x,LL y){
   return a[x]<a[y]?x:y;}
void prepare ()
{sta.push(1);L[1]=0;for (LL u=2;u<=n;u++){while (!sta.empty()){LL x=sta.top();if (a[x]>=a[u]) sta.pop();else break;}if (sta.empty()) L[u]=0;else L[u]=sta.top()+1;sta.push(u);}while (!sta.empty())sta.pop();sta.push(n);R[n]=n+1;for (LL u=n-1;u>=1;u--){while (!sta.empty()){LL x=sta.top();if (a[x]>=a[u]) sta.pop();else break;}if (sta.empty()) R[u]=n+1;else R[u]=sta.top()-1;sta.push(u);}for (LL u=n;u>=1;u--) sr[u]=sr[R[u]+1]+(R[u]-u+1)*a[u];for (LL u=1;u<=n;u++) sl[u]=sl[L[u]-1]+(u-L[u]+1)*a[u];/*for (LL u=1;u<=n;u++) printf("%lld ",sl[u]);printf("\n");for (LL u=1;u<=n;u++) printf("%lld ",sr[u]);printf("\n");*/
}
void pre_st ()
{lg[0]=-1;for (LL u=1;u<=n;u++) lg[u]=lg[u>>1]+1;pw[0]=1;for (LL u=1;u<=18;u++) pw[u]=pw[u-1]<<1;for (LL u=1;u<=n;u++)   st[u][0]=u;for (LL u=1;u<=18;u++){for (LL i=1;i<=n;i++){st[i][u]=st[i][u-1];if (i+pw[u-1]<=n) st[i][u]=getmin(st[i][u-1],st[i+pw[u-1]][u-1]);}}
}
LL Ans[N];
LL calc (LL x,LL y)
{if (x>y) swap(x,y);LL l=lg[y-x+1];return getmin(st[x][l],st[y-pw[l]+1][l]);
}
LL Ri (LL l,LL r)
{LL p=calc(l,r);return a[p]*(p-l+1)+sl[r]-sl[p];
}
LL Li (LL l,LL r)
{LL p=calc(l,r);return a[p]*(r-p+1)+sr[l]-sr[p];
}
void solve ()
{LL l=1,r=1;LL ans=a[1];for (LL u=1;u<=q;u++){while (r<s[u].r) ans=ans+Ri(l,++r);while (l<s[u].l) ans=ans-Li(l++,r);while (l>s[u].l) ans=ans+Li(--l,r);while (r>s[u].r) ans=ans-Ri(l,r--);Ans[s[u].id]=ans;}for (LL u=1;u<=q;u++) printf("%lld\n",Ans[u]);
}
int main()
{scanf("%lld%lld",&n,&q);nn=sqrt(n);for (LL u=1;u<=n;u++)  belong[u]=(u-1)/nn+1;for (LL u=1;u<=n;u++)   scanf("%lld",&a[u]);for (LL u=1;u<=q;u++)   {scanf("%lld%lld",&s[u].l,&s[u].r);s[u].id=u;}sort(s+1,s+1+q,cmp);pre_st();prepare();solve();return 0;
}

bzoj4540: [Hnoi2016]序列

题解