题面
题解
考虑CDQ分治。对于(solve(l,r,v))（其中l,r表示当前处理到的区间的左右端点，v是一个vector，存放当前区间内待处理的所有询问的序号）：
-
设(m=(l+r)>>1)。
-
预处理出(f[i][j](1{leq}i{leq}k，l{leq}j{leq}r))，其中(f[i][j]=)
[egin{cases} {以j为左端点，右端点{leq}m，且a[右端点]=i的不下降子序列数}(l{leq}j{leq}m) \ {以j为右端点，左端点{>m，且a[左端点]=i的不下降子序列数(m<j{leq}r)}} end{cases} ]对于(m<j{leq}r)来言，有递推式
[f[i][j]={sumlimits_{m<k<j,a[k]{leq}a[j]}}f[i][k]+[a[j]=i]$$，这一过程可以用树状数组优化，从而在$O((r-l+1)klogk)$时间内完成预处理。 另外，需要将空字符串统计进去，就是把$f[1][m],f[k][m+1]$都加1。 接下来，对$f$进行前缀和，就可以得到$f[i][j]=$ $$egin{cases} {l{leq}左端点，右端点{leq}m，且a[右端点]=i的不下降子序列数}(l{leq}j{leq}m) \ {j{geq}右端点，左端点{>m，且a[左端点]=i的不下降子序列数(m<j{leq}r)}} end{cases}] -
遍历所有序号(id{in}v)。如果(R[id]{leq}m),将其加入数组vl。如果(L[id]>m)，将其加入数组vr。
-
对于其余id，统计答案：
[{sumlimits_{i=1}^{k}}f[i][L[id]]{sumlimits_{j=i}^{k}}f[j][R[id]]$$。这一过程可以先计算前缀和来优化。 ]
依此过程，solve中预处理的总复杂度是(O(nklognlogk))，统计答案的总复杂度是(O(qk))。
代码
#include<bits/stdc++.h>
using namespace std;
#define N 50000
#define Q 200000
#define ll long long
#define mod 1000000007
#define rg register
namespace ModCalc{
inline void Inc(ll &x,ll y){
x += y;if(x >= mod)x -= mod;
}
inline void Dec(ll &x,ll y){
x -= y;if(x < 0)x += mod;
}
inline ll Add(ll x,ll y){
Inc(x,y);return x;
}
inline ll Sub(ll x,ll y){
Dec(x,y);return x;
}
}
using namespace ModCalc;
inline ll read(){
ll s = 0,ww = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')ww = -1;ch = getchar();}
while('0' <= ch && ch <= '9'){s = 10 * s + ch - '0';ch = getchar();}
return s * ww;
}
inline void write(ll x){
if(x < 0)putchar('-'),x = -x;
if(x > 9)write(x / 10);
putchar('0' + x % 10);
}
ll n,q,k;
ll f[20+5][N+5],a[N+5],L[Q+5],R[Q+5];
ll ans[Q+5];
ll s[20+5];
struct BIT{
ll b[20+5];
inline ll lowbit(ll x){
return x & -x;
}
inline void reset(){
memset(b,0,sizeof(b));
}
inline void ud(ll x,ll dx){
for(rg ll i = x;i <= k;i += lowbit(i))Inc(b[i],dx);
}
inline ll query(ll x){
ll rt = 0;
for(rg ll i = x;i;i -= lowbit(i))Inc(rt,b[i]);
return rt;
}
}B;
inline void solve(ll l,ll r,vector<ll>v){
if(l == r){
for(rg ll i = 0;i < v.size();i++)ans[v[i]] = 2;
return;
}
ll m = (l + r) >> 1;
for(rg ll st = 1;st <= k;st++){
B.reset();
for(rg ll i = m + 1;i <= r;i++){
f[st][i] = B.query(a[i]);
if(a[i] == st)Inc(f[st][i],1);
B.ud(a[i],f[st][i]);
}
for(rg ll i = m + 2;i <= r;i++)Inc(f[st][i],f[st][i-1]);
}
for(rg ll st = 1;st <= k;st++){
B.reset();
for(rg ll i = m;i >= l;i--){
f[st][i] = B.query(k + 1 - a[i]);
if(a[i] == st)Inc(f[st][i],1);
B.ud(k + 1 - a[i],f[st][i]);
}
for(rg ll i = m - 1;i >= l;i--)Inc(f[st][i],f[st][i+1]);
}
for(rg ll i = l;i <= m;i++)Inc(f[1][i],1); //左半部分为空子串
for(rg ll i = m + 1;i <= r;i++)Inc(f[k][i],1); //右半部分为空子串
vector<ll>vl,vr;
vl.resize(0);
vr.resize(0);
for(rg ll i = 0;i < v.size();i++){
ll id = v[i];
if(R[id] <= m)vl.push_back(id);
else if(L[id] > m)vr.push_back(id);
else{
for(rg ll j = k;j >= 1;j--)s[j] = Add(s[j+1],f[j][R[id]]);
for(rg ll j = 1;j <= k;j++)Inc(ans[id],f[j][L[id]] * s[j] % mod);
}
}
if(vl.size())solve(l,m,vl);
if(vr.size())solve(m+1,r,vr);
}
vector<ll>v;
int main(){
n = read(),k = read();
for(rg ll i = 1;i <= n;i++)a[i] = read();
q = read();
for(rg ll i = 1;i <= q;i++)L[i] = read(),R[i] = read();
v.resize(0);
for(rg ll i = 1;i <= q;i++)v.push_back(i);
solve(1,n,v);
for(rg ll i = 1;i <= q;i++)write(ans[i]),putchar('
');
return 0;
}