http://codeforces.com/problemset/problem/91/B

題意：

給你n個數，求得i 到n中小于a[i]的最右邊的a[j],然后求a[i]到a[j]之間包含了多少個數。

思路：

首先自己在做這道題的時候沒有認真讀題，直接把題意搞成求得i 到n中小于a[i]的最右邊的a[j],然后求a[i]到a[j]之間包含了多少個小于a[i]的數了。。。結果樣例都沒過。唉自己還是太粗心，一定要認真把題意搞清楚，然后把想法想好了再敲。不過也算是做了另一道題目吧。

首先我的思路，好像比較復雜。 我們利用線段樹維護小于a[i]的區間[1,a[i]]的最大坐標值，當然要將數列離散話，因為a[i]最大為10^9 而n最大是10^5 .每次插入數據更新區間最值，然后就是求出該區間最值與當前坐標比較求個數。

View Code By E_star, contest: Codeforces Beta Round #75 (Div. 1 Only), problem: (B) Queue, Accepted, ##include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a,b) (a) > (b)? (b):(a) #define Max(a,b) (a) > (b)? (a):(b)#define ll long long #define inf 0x7f7f7f7f #define MOD 1073741824 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 1000007 #define N 1000007 using namespace std; //freopen("data.in","r",stdin);struct node{int val;int pos; }a[N]; int X[N]; int val[N*4]; int pos[N];void pushup(int rt){val[rt] = max(val[rt<<1],val[rt<<1|1]); } void update(int pos,int sc,int l,int r,int rt){if (l == r){val[rt] = sc;return ;}int m = (l + r)>>1;if (pos <= m) update(pos,sc,lc);else update(pos,sc,rc);pushup(rt); } int query(int L,int R,int l,int r,int rt){if (l >= L && r <= R){return val[rt];}int res = 0;int m = (l + r)>>1;if (L <= m) res = max(res,query(L,R,lc));if (R > m) res = max(res,query(L,R,rc));return res; } int bSearch(int p,int L,int R){int l = L;int r = R;int ans = 0;while (l <= r){int m = (l + r)>>1;if (X[m] <= p){l = m + 1;ans = m;}else{r = m - 1;}//puts("<<<<"); }return ans; }int main(){//freopen("data.in","r",stdin);int i;int n;while (~scanf("%d",&n)){for (i = 1; i <= n; ++i){scanf("%d",&a[i].val);a[i].pos = i;X[i] = a[i].val;}//離散化sort(X + 1,X + 1 + n);int k = 1;for (i = 2; i <= n; ++i){if (X[i] != X[i - 1]) X[++k] = X[i];}//每插進一個點就更新[1,a[i]]區間最值CL(val,0);for (i = 1; i <= n; ++i){pos[i] = bSearch(a[i].val,1,k);update(pos[i],a[i].pos,1,k,1);}for (i = 1; i < n; ++i){int p = bSearch(a[i].val - 1,1,k);//二分查找第一個小于a[i]的值if (p == 0){printf("-1 ");continue;}int ans = query(1,p,1,k,1);//詢問該區間的最大坐標if (ans <= a[i].pos) printf("-1 ");else{ans = ans - a[i].pos - 1;printf("%d ",ans);}}printf("-1\n");}return 0; }

?

別人的思路，思考方向不一樣，做法就不一樣。我覺得這個想法很簡潔明了。他直接記錄區間最值，枚舉每個a[i]每次把枚舉到的a[i]更新成inf，線段樹求出整個區間最小值，與該值比較，如果大于等于它肯定輸出-1,否則線段樹里求右邊第一個小于a[i]的值的坐標。 （這里最巧妙數的求最右邊第一個小于a[i]的坐標，以前沒接觸過這個求法）

View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a,b) (a) > (b)? (b):(a) #define Max(a,b) (a) > (b)? (a):(b)#define ll long long #define inf 0x7f7f7f7f #define MOD 1073741824 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 1000007 #define N 1000007 using namespace std; //freopen("data.in","r",stdin);int a[N],val[N];void pushup(int rt){val[rt] = min(val[rt<<1],val[rt<<1|1]); } void build(int l,int r,int rt){if (l == r){scanf("%d",&val[rt]);a[l] = val[rt];return ;}int m = (l + r)>>1;build(lc);build(rc);pushup(rt); } void update(int pos,int l,int r,int rt){if (l == r){val[rt] = inf;return ;}int m = (l + r)>>1;if (pos <= m) update(pos,lc);else update(pos,rc);pushup(rt); } int query(int sc,int l,int r,int rt){if (l == r) return l;int m = (l + r)>>1;if (val[rt<<1|1] < sc) return query(sc,rc);else return query(sc,lc); } int main(){//freopen("data.in","r",stdin);int i;int n;while (~scanf("%d",&n)){build(1,n,1);for (i = 1; i <= n; ++i){update(i,1,n,1);if (val[1] >= a[i]){printf("-1%c",i == n ? '\n' : ' ');}else{int pos = query(a[i],1,n,1);printf("%d%c",pos - i - 1,i == n ? '\n' : ' ');}}}return 0; }

?

轉載于:https://www.cnblogs.com/E-star/archive/2012/10/23/2736202.html

總結

以上是生活随笔為你收集整理的Codeforces Beta Round #75 (Div. 1 Only) B. Queue 线段树。单点更新的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。