/* 換一種更高效的方法。之前的方法之所以超時，是因為找第K大數的方法很慢。 查找第K大，可以利用樹狀數組和二分的方法，二分答案，然后樹狀數組高效回答這個答案是否靠譜 很多細節需要注意，WA,TLE N多 */// include file #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cctype> #include <ctime>#include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <bitset>#include <algorithm> #include <string> #include <vector> #include <queue> #include <set> #include <list> #include <functional>using namespace std;// typedef typedef long long LL; typedef unsigned long long ULL;// #define read freopen("in.txt","r",stdin) #define write freopen("out.txt","w",stdout)#define Z(a) (a<<1) #define Y(a) (a>>1)const double eps = 1e-6; const double INFf = 1e100; const int INFi = 1000000000; const LL INFll = (LL)1<<62; const double Pi = acos(-1.0);template<class T> inline T sqr(T a){return a*a;} template<class T> inline T TMAX(T x,T y) {if(x>y) return x;return y; } template<class T> inline T TMIN(T x,T y) {if(x<y) return x;return y; } template<class T> inline T MMAX(T x,T y,T z) {return TMAX(TMAX(x,y),z); } template<class T> inline T MMIN(T x,T y,T z) {return TMIN(TMIN(x,y),z); } template<class T> inline void SWAP(T &x,T &y) {T t = x;x = y;y = t; }// code begin int N,M; //100000 50000 struct node {int v;int dx;friend bool operator<(node a,node b){return a.v<b.v;} }; node data[100010]; int dx[100010]; //離散化后的結果 int rdx[100010]; // 反映射struct range {int l;int r;int k;int dx;friend bool operator<(range a,range b){return a.l< b.l;} }; range rg[50011]; //區間不交集 int ans[50011];int Bit[100010]; int Nx;inline int lowBit(int x) {return x&(-x); }void update(int x,int c) {for(int i=x;i<Nx;i+=lowBit(i)){Bit[i] += c;} }int getSum(int x) {int sum = 0;for(int i=x;i>0;i-=lowBit(i)){sum += Bit[i];}return sum ; }int main() {read;write;while(scanf("%d %d",&N,&M)==2){for(int i=1;i<=N;i++){scanf("%d",&data[i].v);data[i].dx = i;}for(int i=1;i<=M;i++){scanf("%d %d %d",&rg[i].l,&rg[i].r,&rg[i].k);rg[i].dx = i;}sort(data+1,data+N+1); //排序是為了重新編號Nx = 1;for(int i=1;i<=N;i++) //在這里相同的數也算兩個{rdx[Nx] = data[i].v;dx[data[i].dx] = Nx++;}// 離散完成了// 由于區間不重疊，所以對區間排序sort(rg+1,rg+M+1);// int l,r,mid,tmp;memset(Bit,0,sizeof(Bit));for(int i=1;i<=M;i++){//memset(Bit,0,sizeof(Bit)); 為了避免這個費事的初始化if(i>1) for(int j=rg[i-1].l;j<=rg[i-1].r&&j<rg[i].l;j++){update(dx[j],-1);}for(int j=i>1?(rg[i].l>rg[i-1].r?rg[i].l:(rg[i-1].r+1)):rg[i].l;j<=rg[i].r;j++) //這里出錯很久,千萬不要想當然{//printf("%d ",dx[j]);update(dx[j],1);}//printf("\n");// 二分答案l = 1;r = Nx;while(l<r){mid = Y(l+r);tmp = getSum(mid);if(tmp>=rg[i].k) {r = mid;}else{l = mid+1;}}ans[rg[i].dx] = rdx[r];}for(int i=1;i<=M;i++){printf("%d\n",ans[i]);}}return 0; }

轉載于:https://www.cnblogs.com/ac2012/archive/2011/04/14/2015946.html

總結

以上是生活随笔為你收集整理的2761的全部內容，希望文章能夠幫你解決所遇到的問題。

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