傳送：主席樹做法http://www.cnblogs.com/candy99/p/6160704.html

---

?

做那倒帶修改的主席樹時就發現分塊可以做，然后就試了試

思想和教主的魔法差不多，只不過那個是求>=v的有幾個

既然一個數v的名次可以求，我們二分這個數就行了啊

然而......

首先，你二分到的這個數不一定在區間里出現過

比如 1 2 5 8 9

4和5的名次都是3

于是，我修改了某個區間名次的定義：

“如果一個數的名次是x，但是區間中沒有次數，那么他的名次為x-1”

實現上只需要find里return l-t+(b[l]==v) 等于說明出現過

然而

---

?

---

?

---

?

---

?

該死不寫了鬼知道怎么回事用主席樹就行了

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; const int N=1e5+500; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}return x*f; } int n,Q,a[N],bl,m,b[N],pos[N]; int mp[N]; void reset(int x){int l=(x-1)*bl+1,r=min(x*bl,n);for(int i=l;i<=r;i++) b[i]=a[i];sort(b+l,b+r+1); } int flag; int find(int x,int v){int l=(x-1)*bl+1,r=min(x*bl,n),t=l;while(l<=r){int mid=(l+r)>>1;if(b[mid]<v) l=mid+1;else r=mid-1;}if(b[l]==v) flag=1;return l-t+1;//! } int rank(int l,int r,int v){int ans=0;flag=0;if(pos[l]==pos[r]){for(int i=l;i<=r;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v;}else{int t=pos[l]*bl;for(int i=l;i<=t;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v;for(int i=(pos[r]-1)*bl+1;i<=r;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v;for(int i=pos[l]+1;i<pos[r];i++) ans+=find(i,v);}if(!flag) ans--;return ans; } int query(int ql,int qr,int k){int l=1,r=n;while(l<=r){int mid=(l+r)>>1;int t=rank(ql,qr,mp[mid]);if(t<k) l=mid+1;else r=mid-1;}return l; } int main(){freopen("in.txt","r",stdin);freopen("1.out","w",stdout);n=read();Q=read();bl=sqrt(n);m=n/bl;if(n%bl) m++;for(int i=1;i<=n;i++) a[i]=mp[i]=read(),pos[i]=(i-1)/bl+1;for(int i=1;i<=m;i++) reset(i);sort(mp+1,mp+1+n);while(Q--){int i=read(),j=read(),k=read();printf("%d\n",mp[query(i,j,k)]);} } View Code #include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #pragma comment(linker,"/STACK:102400000,102400000")using namespace std; #define MAX 100005 #define MAXN 1000005 #define maxnode 15 #define sigma_size 30 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lrt rt<<1 #define rrt rt<<1|1 #define middle int m=(r+l)>>1 #define LL long long #define ull unsigned long long #define mem(x,v) memset(x,v,sizeof(x)) #define lowbit(x) (x&-x) #define pii pair<int,int> #define bits(a) __builtin_popcount(a) #define mk make_pair #define limit 10000//const int prime = 999983; const int INF = 0x3f3f3f3f; const LL INFF = 0x3f3f; const double pi = acos(-1.0); const double inf = 1e18; const double eps = 1e-8; const LL mod = 1e9+7; const ull mx = 133333331;/*****************************************************/ inline void RI(int &x) {char c;while((c=getchar())<'0' || c>'9');x=c-'0';while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';} /*****************************************************/int a[MAX]; int b[MAX]; int c[MAX]; int tmp; bool judge(int x,int l,int r,int k){int a1=l/tmp;int a2=r/tmp;int sum=0;//for(int i=l;i<=r;i++) printf("%d ",a[i]);puts("");if(a1==a2){for(int i=l;i<=r;i++) if(a[i]<=c[x]) sum++;if(sum>=k) return true;return false;}for(int i=a1+1;i<a2;i++){sum+=upper_bound(b+i*tmp,b+(i+1)*tmp,c[x])-b-i*tmp;}for(int i=l;i<(a1+1)*tmp;i++) if(a[i]<=c[x]) sum++;for(int i=a2*tmp;i<=r;i++) if(a[i]<=c[x]) sum++;//printf("ra %d %d %d %d\n",l,r,c[x],sum);if(sum>=k) return true;return false; }int main(){freopen("in.txt","r",stdin);freopen("2.out","w",stdout);int n,m;scanf("%d%d",&n,&m);tmp=sqrt(n);for(int i=0;i<n;i++){scanf("%d",&a[i]);b[i]=a[i];c[i]=a[i];}sort(c,c+n);for(int i=0;i*tmp<n;i++){if((i+1)*tmp<=n) sort(b+i*tmp,b+(i+1)*tmp);else sort(b+i*tmp,b+n);}while(m--){int l,r,k;scanf("%d%d%d",&l,&r,&k);int ll=0,rr=n-1;while(ll<=rr){int mid=(ll+rr)>>1;if(judge(mid,l-1,r-1,k)) rr=mid-1;else ll=mid+1;}printf("%d\n",c[ll]);}return 0; } 別人的AC代碼

?

轉載于:https://www.cnblogs.com/candy99/p/6195716.html

總結

以上是生活随笔為你收集整理的POJ2104 K-th Number [分块做法]的全部內容，希望文章能夠幫你解決所遇到的問題。

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