FJUT3260

不是啊。。不是说双栈嘛，，怎么是个**题啊。

链接：

 http://120.78.128.11/Problem.jsp?pid=3260 

 

从左到右扫一遍，把相交的区间扔到一起算，那么就变成了一个前缀后缀积的问题。。

感觉还是挺有思维难度的？(也可能是我今天降智)

写起来还是很好写的，1A了。

 #include <bits/stdc++.h>

 using namespace std;

 inline int read() {

     int X=,w=; char c=getchar();

     while (c<''||c>'') { if (c=='-') w=-; c=getchar(); }

     while (c>=''&&c<='') X=(X<<)+(X<<)+c-'',c=getchar();

     return X*w;

 }

 typedef long long ll;

 ll pre[],las[];

 int n,p,c[],q,a[],b[],ans[];

 int main(){

     n=read();p=read();

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

     q=read();

     for(int i=;i<=q;i++)a[i]=read(),b[i]=read();

     for(int l=,r;l<=q;l=r+){

         r=l;

         while (a[r]<=b[l]&&r<=q)r++;

         r--;

         //[l,r]是分成一段

         pre[] = c[b[l]];

         for(int i=;b[l]-i>=a[l];i++){//左边

             pre[i] = pre[i-]*c[b[l]-i]%p;

         }

         las[]=;

         for(int i=;b[l]+i<=b[r];i++){//右边

             las[i]=las[i-]*c[b[l]+i]%p;

         }

         for(int i=l;i<=r;i++){//统计答案

             ans[i]=pre[b[l]-a[i]]*las[b[i]-b[l]]%p;

         }

     }

     for(int i=;i<=q;i++){

         printf("%d\n",ans[i]);

     }

 }