[数据结构与算法]小沙的remake（牛客）排序+ 树状数组 + dp

原题链接：登录—专业IT笔试面试备考平台_牛客网

把a[i]先排序（带着下标排），然后从小到大每次先找下标在范围之内 [ i ? b i , i ) 的所有种数，然后加一就是以a[i]为最后一个元素的所有种数。

因为数据可能会很大，每次更新树状数组中的值的时候记得取模。如果有相减的时候，记得要加mod再取模。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

#include<bits/stdc++.h>
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;
using namespace std;
const int N=2e6+7,mod=1e9+7;
int a[N],b[N];
PII p[N];
int n,seed;

int tree[N];

int lowbit(int x){
	return x&(-x);
}

inline void update(int p, int sum){
	while (p <= n){
		tree[p] = (tree[p] + sum) % mod;
		p += lowbit(p);
	}
}

inline int query(int p){
	int ans = 0;
	while (p > 0){
		ans = (ans + tree[p]) % mod;
		p -= lowbit(p);
	}
	return ans;
}

int main(){
    scanf("%d %d",&n,&seed);
	srand(seed);
	for(int i=1;i<=n;i++){
		a[i]=read(0),b[i]=read(i);
	}
	rep(i, n) p[i] = {a[i], i};
	sort(p + 1, p + 1 + n);
	rep(i, n)
	{
	    int id = p[i].second;
	    int sum = (query(id - 1) - query(id - b[id] - 1) + 1 + mod) % mod; //只有当时这个数也是一种
	    update(id, sum);
	}
	printf("%d", query(n));
    return 0;
}