题目：
题意：100000个数的序列，有100000次询问，每次问区间最大值大于等于k的区间有多少？
思路：一开始没看到“大于等于”，想了很久也不会，原来看错题了。看错题害死人。
一般询问的问题，如果不能用线段树log(n)求出，那么就离线做。
首先将询问按从大到小排序，再将序列中的每个数排序，注意记录序号。
对于当前询问，每加进一个数，我需要找到它在加进的序列（按大小有序的）上下界，即上下编号high,low.
那么加进这个数的影响就是在【high,low】中选取经过当前id的区间数。所以我用set存储，low_bound查找边界.
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<set>#include<algorithm>using namespace std;const int N = 1e5+10;typedef long long ll;int n,m;struct query{int id;int k;ll ans;}q[N],a[N];int cmp(query a,query b){return a.k > b.k;}int cmp2(query a,query b){return a.id < b.id;}struct num1{int x;bool operator<(const num1& b)const {return x<b.x;}};struct num2{int x;bool operator<(const num2& b)const {return x>b.x;}};set<num1> s1;set<num1>::iterator it1;set<num2> s2;set<num2>::iterator it2;void solve(){s1.clear(); s2.clear();int p1=1,p2=1;ll ans = (ll)n*(n-1)/2 + n;ll co = 0;while(p2<=m){int wt = q[p2].k;while(a[p1].k>=wt && p1<=n){int idt = a[p1].id;num1 tmp1; tmp1.x = idt;num2 tmp2; tmp2.x = idt;s1.insert(tmp1);s2.insert(tmp2);it1 = s1.upper_bound(tmp1);it2 = s2.upper_bound(tmp2);int high,low;if(it1==s1.end()) high=n;else high = (*it1).x-1;if(it2==s2.end()) low=1;else low = (*it2).x+1;co += (ll)(idt-low)*(high-idt) + (high-low+1);p1++;}q[p2].ans = co;p2++;}}int main(){cin >> n ;for(int i=1;i<=n;i++){scanf("%d",&a[i].k);a[i].id = i;}cin >> m;for(int i=1;i<=m;i++){scanf("%d",&q[i].k);q[i].id = i;}sort(a+1,a+1+n,cmp);sort(q+1,q+1+m,cmp);solve();sort(q+1,q+1+m,cmp2);for(int i=1;i<=m;i++)printf("%lld\n",q[i].ans);return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
昨晚多几分钟的准备，今天少几小时的麻烦。
