[loj3247]Non-Decreasing Subsequences

分治，考虑分治到[l,r]的区间（设$mid=(l+r)/2$），将询问分为两类：
1.在左/右区间，直接递归下去；
2.跨越中间，那么处理出两个数组：L[i][j]表示左区间在开头第i个位置，以数字j为结尾的上升子序列个数（不跨越mid），右区间同理
（L和R的计算很简单，只需要再处理出一个L[i][j][k]表示i后面以j为开头，以k为结尾的子序列个数即可）
对其求前/后缀和，那么就求出了开头在第i个位置以后/结尾在第i个位置以前的子序列个数
设询问区间为[x,y]，那么答案就是$\sum_{i=1}^{20}L[x][i]+R[y][i]+L[x][i]\sum_{j=i}^{20}R[y][j]$，注意取模

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define mid (l+r>>1)

 5 #define mod 1000000007

 6 struct ji{

 7     int l,r,id;

 8 }q[N];

 9 int n,m,a[N],ans[N],f[N][21],ff[N][21][21],g[N][21],gg[N][21][21],sum[N][22];

10 void dfs(int l,int r,int x,int y){

11     if (l==r){

12         for(int i=x;i<=y;i++)ans[q[i].id]=1;

13         return;

14     }

15     int p=x;

16     for(int i=x;i<=y;i++)

17         if (q[i].r<=mid)swap(q[p++],q[i]);

18     dfs(l,mid,x,p-1);

19     x=p;

20     for(int i=x;i<=y;i++)

21         if (mid<q[i].l)swap(q[p++],q[i]);

22     dfs(mid+1,r,x,p-1);

23     x=p;

24     memset(f[mid],0,sizeof(f[mid]));

25     memset(ff[mid],0,sizeof(ff[mid]));

26     memset(g[mid],0,sizeof(g[mid]));

27     memset(gg[mid],0,sizeof(gg[mid]));

28     ff[mid][a[mid]][a[mid]]=f[mid][a[mid]]=1;

29     for(int i=mid-1;i>=l;i--)

30         for(int j=1;j<=20;j++){

31             f[i][j]=0;

32             for(int k=1;k<=j;k++){

33                 ff[i][j][k]=ff[i+1][j][k];

34                 if (k==a[i]){

35                     if (j==k)ff[i][j][k]++;

36                     for(int t=k;t<=20;t++)ff[i][j][k]=(ff[i][j][k]+ff[i+1][j][t])%mod;

37                 }

38                 f[i][j]=(f[i][j]+ff[i][j][k])%mod;

39             }

40         }

41     gg[mid+1][a[mid+1]][a[mid+1]]=g[mid+1][a[mid+1]]=1;

42     for(int i=mid+2;i<=r;i++)

43         for(int j=1;j<=20;j++){

44             g[i][j]=0;

45             for(int k=j;k<=20;k++){

46                 gg[i][j][k]=gg[i-1][j][k];

47                 if (k==a[i]){

48                     if (j==k)gg[i][j][k]++;

49                     for(int t=1;t<=k;t++)gg[i][j][k]=(gg[i][j][k]+gg[i-1][j][t])%mod;

50                 }

51                 g[i][j]=(g[i][j]+gg[i][j][k])%mod;

52             }

53         }

54     for(int i=mid+1;i<=r;i++)

55         for(int j=20;j;j--)sum[i][j]=(sum[i][j+1]+g[i][j])%mod;

56     for(int i=x;i<=y;i++)

57         for(int j=1;j<=20;j++)

58             ans[q[i].id]=(ans[q[i].id]+f[q[i].l][j]*(1LL+sum[q[i].r][j])+g[q[i].r][j])%mod;

59 }

60 int main(){

61     scanf("%d%*d",&n);

62     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

63     scanf("%d",&m);

64     for(int i=1;i<=m;i++){

65         scanf("%d%d",&q[i].l,&q[i].r);

66         q[i].id=i;

67     }

68     dfs(1,n,1,m);

69     for(int i=1;i<=m;i++)printf("%d\n",(ans[i]+1)%mod);

70 }

巴特西

[loj3247]Non-Decreasing Subsequences

最新文章

热门文章