[BZOJ]4540: [Hnoi2016]序列-白红宇

[BZOJ]4540: [Hnoi2016]序列

阅读量：4463 次

发布时间：2019-06-08

本文共 2722 字，大约阅读时间需要 9 分钟。

题解: 这个题出发点显然在在左/右加入一个元素对答案产生的贡献首先大方向上离线区间考虑单点贡献我们选择莫队算法问题是我们如何去处理转移的问题

　　　　$$ \sum_{i=l}^{r}min(a[i....r]) $$这个很容易得到然后有个很显然的结论若pos为区间{l,r]的最小值的出现位置那么在右端点加入a[r]时[l,pos]都将是a[pos]产生贡献那么我们现在考虑的是[pos+1,r]这些为左端点时的贡献情况

我们对于每一个点处理出左边第一个比他小的然后这就类似于一颗树形结构那么对于加入的a[r]我们只需要将树上的pos~r这条链的和统计出来即可为什么一定这条链满足情况呢因为a[pos]是区间最小的位置那么对于r必然其祖先节点有一个是pos那么对于[pos+1,r]为左端点的情况我们只需要统计前缀和差分一下就行了然后区间最小值位置用st表求出即可

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define mp make_pair#define pb push_back#define pii pair
               
                #define link(x) for(edge *j=h[x];j;j=j->next)#define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)const int MAXN=3e5+10;const double eps=1e-8;#define ll long longusing namespace std;struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;} int n,m;int p[MAXN],sz,a[MAXN]; typedef struct node{ int id,l,r; friend bool operator<(node aa,node bb){ if(p[aa.l]==p[bb.l])return aa.r
                
                 a[i])tot--; if(!tot)L[i]=0; else L[i]=st[tot]; st[++tot]=i; } inc(i,1,n){ Left[i]=Left[L[i]]+1ll*(i-L[i])*a[i]; } tot=0;R[n]=n+1;st[++tot]=n; dec(i,n-1,1){ while(tot&&a[st[tot]]>a[i])tot--; if(!tot)R[i]=n+1; else R[i]=st[tot]; st[++tot]=i; } dec(i,n,1){ Right[i]=Right[R[i]]+1ll*(R[i]-i)*a[i]; } inc(i,1,n)dp[i][0]=a[i],pos[i][0]=i; inc(j,1,20){ for(int i=1;i+(1<
                 
                  <=n+1;i++){ if(dp[i][j-1]
                  
                   <<(j-1))][j-1])dp[i][j]=dp[i][j-1],pos[i][j]=pos[i][j-1]; else dp[i][j]=dp[i+(1<<(j-1))][j-1],pos[i][j]=pos[i+(1<<(j-1))][j-1]; } } inc(i,2,n)ma[i]=ma[i/2]+1;} int Min(int l,int r){ int k=r-l+1;k=ma[k]; int t1=dp[l][k];int t2=dp[r-(1<
                   
                    que[i].r)ans-=rcalc(l,r),r--; while(l
                    
                     que[i].l)l--,ans+=lcalc(l,r); ans1[que[i].id]=ans; } inc(i,1,m)printf("%lld\n",ans1[i]);}

4540: [Hnoi2016]序列

Time Limit: 20 Sec Memory Limit: 512 MB

Submit: 2129 Solved: 1061

[][][]

Description

　　给定长度为n的序列：a1,a2,…,an，记为a[1:n]。类似地，a[l:r]（1≤l≤r≤N）是指序列：a_l,a_l+1,…,a_r-

1,a_r。若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

HINT

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

转载于:https://www.cnblogs.com/wang9897/p/10347263.html

你可能感兴趣的文章