【BZOJ4540】【HNOI2016】序列 [莫队][RMQ]

序列

Time Limit: 20 Sec Memory Limit: 512 MB
[Submit][Status][Discuss]

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

　　28
　　17
　　11
　　11
　　17

HINT

　　1 ≤N,Q ≤ 100000,|Ai| ≤ 10^9

Solution

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int INF = ;

 int n,m;

 int block[ONE],Q;

 int a[ONE],pL[ONE],pR[ONE];

 int stk[ONE],top;

 int Log[ONE],Bin[ONE],MinD[ONE][],NumD[ONE][];

 s64 Fl[ONE],Fr[ONE];

 s64 ans,Ans[ONE];

 struct power

 {

         int id;

         int l,r;

 }oper[ONE];

 inline bool cmp(const power &a,const power &b)

 {

         if(block[a.l] != block[b.l]) return block[a.l] < block[b.l];

         return a.r < b.r;

 }

 inline int get()

 {

         int res=,Q=;  char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 inline void Pre_Rmq()

 {

         Log[]=-;  for(int i=;i<=n;i++) Log[i] = Log[i>>] + ;

         Bin[]=;   for(int i=;i<=; i++) Bin[i] = Bin[i-] << ;

         for(int j=;j<=;j++)

         for(int i=;i<=n;i++)

         if(i+Bin[j]- <= n)

         {

             int Next = i + Bin[j-];

             if(MinD[i][j-] < MinD[Next][j-])

                 MinD[i][j] = MinD[i][j-], NumD[i][j] = NumD[i][j-];

             else

                 MinD[i][j] = MinD[Next][j-], NumD[i][j] = NumD[Next][j-];

         }

         else break;

 }

 inline int Get(int x,int y)

 {

         int T = Log[y - x +];

         if(MinD[x][T] < MinD[y-Bin[T]+][T]) return NumD[x][T];

         return NumD[y-Bin[T]+][T];

 }

 inline void MakepL()

 {

         top = ;

         for(int i=n;i>=;i--)

         {

             while(top && a[stk[top]] > a[i])

                 pL[stk[top--]] = i;

             stk[++top] = i;

         }

         while(top) pL[stk[top--]] = ;

         for(int i=;i<=n;i++) pL[i]++;

 }

 inline void MakepR()

 {

         top = ;

         for(int i=;i<=n;i++)

         {

             while(top && a[stk[top]] > a[i])

                 pR[stk[top--]] = i;

             stk[++top] = i;

         }

         while(top) pR[stk[top--]] = n+;

         for(int i=;i<=n;i++) pR[i]--;

 }

 inline s64 DealL(int l,int r)

 {

         int pos = Get(l,r);

         return (s64)a[pos] * (r-pos+) + Fr[l] - Fr[pos];

 }

 inline s64 DealR(int l,int r)

 {

         int pos = Get(l,r);

         return (s64)a[pos] * (pos-l+) + Fl[r] - Fl[pos];

 }

 int main()

 {

         n = get();    m = get();    Q = sqrt(n);

         for(int i=;i<=n;i++)

         {

             a[i] = get(); block[i] = (i-)/Q+;

             MinD[i][] = a[i]; NumD[i][] = i;

         }

         Pre_Rmq();    MakepL();    MakepR();

         for(int i=;i<=n;i++) Fl[i] = Fl[pL[i]-] + (s64)(i-pL[i]+) * a[i];

         for(int i=n;i>=;i--) Fr[i] = Fr[pR[i]+] + (s64)(pR[i]-i+) * a[i];

         for(int i=;i<=m;i++)

         {

             oper[i].id = i;

             oper[i].l = get();    oper[i].r = get();

         }

         sort(oper+, oper+m+, cmp);

         int l = , r = ;

         for(int i=;i<=m;i++)

         {

             while(r < oper[i].r) ans += DealR(l,++r);

             while(oper[i].l < l) ans += DealL(--l,r);

             while(r > oper[i].r) ans -= DealR(l,r--);

             while(oper[i].l > l) ans -= DealL(l++,r);

             Ans[oper[i].id] = ans;

         }

         for(int i=;i<=m;i++)

             printf("%lld\n",Ans[i]);

 }

巴特西