题意：
美丽的序列是指：序列中包含一对相邻元素，它们的差小于等于M。
现在给出一个序列，请你计算其中美丽的子序列的个数。
题解：
当初做的时候线段树基本功不扎实没有写出来。隔了三个月再看感觉挺简单的。
由于美丽的序列定义，可以发现美丽的序列实在是太多了，所以解法是反其道而行之，先求出不美丽的序列数量，用总序列数量减去不美丽的序列数量，就是答案。
那么怎么求出不美丽的序列数量呢？
我的做法是开一个dp数组，表示以当前元素结尾的不合法序列的数量。
然后我们从左到右遍历数组，可以推出状态转移方程：
dp的值 = 结尾元素的值和当前元素的值差大于M的子序列数量 + 1。因为它自己也算是一个不合法的子序列。
如何快速查询结尾元素的值在指定区间里的子序列数量呢？这里我调用了线段树维护，每次计算出当前dp值后在线段树里更新，具体见代码，感觉还是挺简单的。
这次千万不要出高难度的DP啊。。。多出数据结构，三维四维滚动数组真顶不住啊。。。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+14; typedef long long ll; const ll mod=1e9+7; struct node { int l; int r; ll sum; }segTree[maxn*5]; int a[maxn]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=0; return; } int mid=(l+r)>>1; build (i<<1,l,mid); build (i<<1|1,mid+1,r); } void add (int i,int t,ll b) { segTree[i].sum+=b; segTree[i].sum%=mod; if (segTree[i].l==t&&segTree[i].r==t) return; int mid=(segTree[i].l+segTree[i].r)>>1; if (t<=mid) add (i<<1,t,b); else add (i<<1|1,t,b); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; segTree[i].sum%=mod; } ll query (int i,int l,int r) { if (l==segTree[i].l&&r==segTree[i].r) return segTree[i].sum%mod; int mid=(segTree[i].l+segTree[i].r)>>1; if (r<=mid) return query(i<<1,l,r)%mod; else if (l>mid) return query(i<<1|1,l,r)%mod; else return query(i<<1,l,mid)%mod+query(i<<1|1,mid+1,r)%mod; } ll dp[maxn]; int main () { int N,M; ll ans=1; scanf("%d%d",&N,&M); //if (N==1e5) while(1); for (int i=1;i<=N;i++) scanf("%d",&a[i]),a[i]+=1e5; //printf("%lld ",ans); build(1,1,maxn); for (int i=1;i<=N;i++) { dp[i]=(query(1,1,a[i]-M-1)%mod+query(1,a[i]+M+1,maxn)%mod+1)%mod; //dp[i]%=mod; add(1,a[i],dp[i]); } ll tt=0; for (int i=1;i<=N;i++) tt+=dp[i],tt%=mod; for (int i=1;i<=N;i++) { ans<<=1; ans%=mod; } //tt%=mod; ans=ans+mod-(tt+1)%mod; ans%=mod; //ans=0; printf("%lld ",ans); }