Codeforces Beta Round #75 (Div. 1 Only) B. Queue 线段树+二分

2019-11-06 06:24:41

字体：大中小

来源：转载

供稿：网友

题目链接:

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

题意:

给你一个数列，让你找到最右边比这个数小的数的位置，如果没有就输出-1

题解:

线段树中二分，查询最小值，然后二分区间就好了

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 1e5+10;int a[maxn],tree[maxn<<2],ans[maxn],cnt;void pushup(int rt){ tree[rt] = min(tree[rt<<1],tree[rt<<1|1]);}void build(int rt,int l,int r){ tree[rt] = INF; if(l == r){ tree[rt] = a[l]; return ; } int mid = (l+r)/2; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt);}void query(int rt,int l,int r,int x){ if(l == r){ ans[++cnt] = l-x-1; return ; } int mid = (l+r)/2; if(tree[rt<<1|1] < a[x]) query(rt<<1|1,mid+1,r,x); else query(rt<<1,l,mid,x);}void update(int rt,int l,int r,int x){ if(l == r){ tree[rt] = INF; return ; } int mid = (l+r)/2; if(x>mid) update(rt<<1|1,mid+1,r,x); else update(rt<<1,l,mid,x); pushup(rt);}int main(){ int n = read(); for(int i=1; i<=n; i++) a[i] = read(); build(1,1,n); for(int i=1; i<=n; i++){ if(tree[1] >= a[i]) ans[++cnt] = -1; else query(1,1,n,i); update(1,1,n,i); } for(int i=1; i<=cnt; i++) cout << ans[i] << " "; cout << endl; return 0;}// http://codeforces.com/problemset/problem/91/B

上一篇：BZOJ3060: [Poi2012]Tour de Byteotia

下一篇：ARIMA模型的拖尾截尾问题

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注