小沙的remake（普通版）

tag:

• 线段树，树状数组，dp
• cf分段1800+

两个题就一起讲了：

找到连续的，上升子序列且下标之差满足某个范围
求方案数

题目挺简单的，特别是你如果马上能利用dp计数方案的思维去思考这题，就会立马发现这题首先要做的一点就是存储下标+排序

排序完了之后就是寻找当数字之前且下标也在他之前的方案数量，存储到当前数字的下标的数组里。

这个维护手段就是树状数组，所以如果能把dp和树状数组结合起来，这题就是秒切了。

#include<bits/stdc++.h>
using namespace std;

namespace GenHelper
{
    int z1,z2,z3,z4,z5,u,res;
    int get()
    {
        z5=((z1<<6)^z1)>>13;
        z1=((int)(z1&4294967)<<18)^z5;
        z5=((z2<<2)^z2)>>27;
        z2=((z2&4294968)<<2)^z5;
        z5=((z3<<13)^z3)>>21;
        z3=((z3&4294967)<<7)^z5;
        z5=((z4<<3)^z4)>>12;
        z4=((z4&4294967)<<13)^z5;
        return (z1^z2^z3^z4);
    }
    int read(int m) {
        u=get();
        u>>=1;
        if(m==0)res=u;
        else res=(u/2345+1000054321)%m;
        return res;
    }
     void srand(int x)
    {
        z1=x;
        z2=(~x)^(0x23333333);
        z3=x^(0x12345798);
        z4=(~x)+51;
      	u = 0;
    }
}
using namespace GenHelper;

const int N=2e6+7,mod=1e9+7;
int a[N],b[N];
pair<int,int>x[N];
#define ll long long
ll tre[N];
int lowbit(int x){
    return x&(-x);
}
int n;
void add(int x,int k){
    while(k<=n){
        tre[k]= (tre[k] + x) % mod;
        k+=lowbit(k);
    }
}
ll getsum(int k){
    ll sum = 0;
    while(k){
        sum=(tre[k] + sum ) % mod;
        k-=lowbit(k);
    }
    return sum;
}
int main(){
    int seed;
    scanf("%d %d",&n,&seed);
	srand(seed);
	for(int i=1;i<=n;i++){
		a[i]=read(0),b[i]=read(i);
        x[i].first = a[i];
        x[i].second = i;
	}
    sort(x+1,x+n+1);
    ll sum = 0;
    for(int i = 1 ; i<= n ; i++) {
        ll kmm = (getsum(x[i].second) - getsum(x[i].second - b[x[i].second] - 1) + 1 + mod) % mod;
        add(kmm,x[i].second);
    }
    cout<<getsum(n);
    return 0;
}