题目链接：http://codeforces.com/contest/1167
E - Range Deleting 题意：给n个数，每个数a[i]的数值范围为 1 < = a [ i ] < = x 1<=a[i]<=x 1<=a[i]<=x，1<= n,x <=1000000 定义 f ( l , r ) f(l,r) f(l,r)为去掉 l < = a [ i ] < = r l<=a[i]<=r l<=a[i]<=r后的数组，如果这个数组是非递减的，则是符合条件的，问有多少对(l,r)满足条件，并输出这个对数。 题解：预处理，求出现在每个值v前面的，最大值val2，大于v的最小值val；
#include<cstdio> #include<iostream> #include<algorithm> #include<set> #include<cstring> using namespace std; #define ll long long const int maxn=1000010; struct node{ int val,val2; }ve[maxn]; int main() { int n,x; while(~scanf("%d%d",&n,&x)){ for(int i=1;i<=x;i++){ ve[i].val=ve[i].val2=-1; } set<int> st; int a,mx=0,cur; int hi=1,po=x;// for(int i=1;i<=n;i++){ scanf("%d",&a); if(a<mx){ hi=max(hi,a);//比前面数小的 最大数 cur=*st.upper_bound(a); if(ve[a].val==-1){ ve[a].val=cur; }else{ ve[a].val=min(ve[a].val,cur); } ve[a].val2=max(ve[a].val2,mx); }else mx=a; st.insert(a); } ll ans=0; for(int i=1;i<=po;i++){ hi=max(hi,i); //printf("i:%d cur:%d\n",i,x-hi+1);// ans+=(x-hi+1);//删去区间为[i,hi]到[i,x] if(ve[i].val2!=-1) hi=max(ve[i].val2,hi);//保留i，则[i+1,val2]都要删去 if(ve[i].val!=-1) po=min(ve[i].val,po);//保留val，则i不能保留，故取值上限限定 } printf("%I64d\n",ans); } return 0; } /* 3 3 3 1 3 3 3 1 2 3 */