題意：給出n個數字，和m次詢問，每次詢問區間【a,b】中第k大的數字，並且輸出。 這裡用到了一種數據結構，劃分樹。 劃分樹指的是，每一個節點保存區間[l,r]所有元素，元素排列順序與原數組相同，但是兩個子樹的元素為該節點所有元素排序後前(r-l+1)/2個進入左子樹，其余的到右子樹，同時維護一個sum域，sum[i]表示l--i這些點中有多少個進入了左子樹。 關於其查找，在[l,r]區間內，查找第k大數，t是該節點，tree[t].l,tree[t].r是該節點的左右區間。mid是區間中值。 1、sum[r]-sum[l-1]>=k，查找LL(t),區間對應為[ tree[t].l+sum[l-1] , tree[t].l+sum[r]-1 ] 2、sum[r]-sum[l-1]<k,查找RR(t)，區間對應為[ mid+1+l-tree[t].l-sum[l-1] , mid+1+r-tree[t].l-sum[r] ] 具體見代碼 [cpp] #include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 100005 #define inf 1<<28 #define LL(x) (x<<1) #define RR(x) (x<<1|1) #define FOR(i,s,t) for(int i=(s);i<=(t);++i) #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) using namespace std; int lessmid[20][Max];//在區間內小於mid值的個數。 int seg[20][Max]; int num[Max]; struct seg_tree { int l ,r ; } tree[Max*4]; void build_tree(int l,int r, int u,int d) { tree[u].l = l, tree[u].r = r; if(l == r)return ; int mid = l + r >> 1; int issame = mid - l + 1;//左邊一共可以有多少元素 for (int i = l ; i <= r ; i ++) if(seg[d][i] < num[mid])//小於中間值的全部放在左邊 issame --;//issame-- ,表示這個值可以放在左邊，那麼左邊的剩余總數減少。 //最終issame總數是表示放等於中值的數字的個數。 int lpos = l ,rpos = mid + 1; for (int i = l ; i <= r ; i ++) { if( i == l ) lessmid[d][i] = 0;//lessmid[d][i]記錄在第d層,[l,i]之間小於等於中值的數的個數。 else lessmid[d][i] = lessmid[d][i-1]; if(seg[d][i] < num[mid]) { lessmid[d][i] ++;//小於中值，計數加 seg[d+1][lpos++] = seg[d][i];//將此數放到左邊 } else if(seg[d][i] > num[mid]) { seg[d+1][rpos++] = seg[d][i];//同理 } else//若相等，則需用到上面的issame元素. { if(issame > 0)//如果issame > 0 ，那麼左邊還沒放滿，則可以將等於中值的數放到左邊。 { issame --; lessmid[d][i]++;//這裡加的就是等於中值的個數。 seg[d+1][lpos++] = seg[d][i]; } else seg[d+1][rpos++] = seg[d][i]; } } build_tree(l,mid,LL(u),d+1); build_tree(mid+1,r,RR(u),d+1); } int update(int l,int r,int u,int d,int cnt) { if(l == r)return seg[d][l]; int num1 ,num2; if(l == tree[u].l) { num1 = lessmid[d][r]; num2 = 0; } else { num1 = lessmid[d][r] - lessmid[d][l-1];//[l,r]的小於等於中值的個數，放到左邊 num2 = lessmid[d][l-1];//[tree[u].l,l-1]的小於等於中值的個數,放到左邊 } if(num1 >= cnt) { return update(tree[u].l + num2,tree[u].l + num1 + num2 - 1,LL(u),d+1,cnt); } else { int mid = tree[u].l + tree[u].r >> 1; int num4 = l - tree[u].l - num2;//[tree[u].l , l - 1]放到右邊的總數。 int num3 = r - l + 1- num1 ;//[l,r]放到右邊的總數。 return update(mid + num4 + 1 , mid + num3 +num4 ,RR(u),d+1 ,cnt - num1); } } int main() { int n , m ; cin >> n >> m ; for (int i = 1 ; i <= n ; i ++) { scanf("%d",&num[i]); seg[1][i] = num[i]; } sort(num + 1,num + n + 1 ); build_tree(1,n,1,1); while(m --) { int a, b ,c; scanf("%d%d%d",&a,&b,&c); printf("%d\n",update(a,b,1,1,c)); } return 0; }
