傳送門

文章目錄

• 題意：
• 思路：

題意：

給一個長度為$n$的序列，每次一個詢問$[l,r]$，求其中數(shù)第一次出現(xiàn)的位置的中位數(shù)。

思路：

先考慮一下如何求區(qū)間內(nèi)不同數(shù)的個數(shù)。
因為要求位置的中位數(shù)，我們考慮以位置建立線段樹。因為要求第一次出現(xiàn)的位置，我們倒著插入，記$pre[i]$為$i$上次出現(xiàn)的位置，每次插入的時候都將當(dāng)前數(shù)的位置$+1$，$pre[i]$的位置$?1$，讓后可持久化一下，這樣當(dāng)詢問$[l,r]$的時候就直接詢問第$l$棵樹的$[l,r]$內(nèi)的和。
我們求出來了區(qū)間不同數(shù)的個數(shù)$sum$，那么中位數(shù)的位置就是$?\frac{sum+1}{2}?$，也就是查詢第$l$棵樹的第$?\frac{sum+1}{2}?$個大數(shù)即可。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; int a[N],pre[N]; int root[N],tot; struct Node {int l,r;int sum; }tr[N*40];void insert(int p,int &q,int l,int r,int x,int c) {q=++tot; tr[q]=tr[p];tr[q].sum+=c;if(l==r) return;int mid=l+r>>1;if(x<=mid) insert(tr[p].l,tr[q].l,l,mid,x,c);else insert(tr[p].r,tr[q].r,mid+1,r,x,c); }int query_sum(int u,int l,int r,int ql,int qr) {if(!u) return 0;if(ql<=l&&r<=qr) return tr[u].sum;int mid=l+r>>1,ans=0;if(ql<=mid) ans+=query_sum(tr[u].l,l,mid,ql,qr);if(qr>mid) ans+=query_sum(tr[u].r,mid+1,r,ql,qr);return ans; }int query_k(int u,int l,int r,int k) {if(l==r) return l;int mid=l+r>>1;if(tr[tr[u].l].sum>=k) return query_k(tr[u].l,l,mid,k);else return query_k(tr[u].r,mid+1,r,k-tr[tr[u].l].sum); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);int _; scanf("%d",&_);for(int __=1;__<=_;__++){scanf("%d%d",&n,&m); tot=0;for(int i=1;i<=n;i++) root[i]=0; root[n+1]=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=n;i>=1;i--){insert(root[i+1],root[i],1,n,i,1);if(pre[a[i]]) insert(root[i],root[i],1,n,pre[a[i]],-1);pre[a[i]]=i;}int p=0;printf("Case #%d:",__);while(m--){int ql,qr; scanf("%d%d",&ql,&qr);int l=min((ql+p)%n+1,(qr+p)%n+1);int r=max((ql+p)%n+1,(qr+p)%n+1);int sum=query_sum(root[l],1,n,l,r);int mid=(sum+1)/2;printf(" %d",p=query_k(root[l],1,n,mid));}puts("");for(int i=1;i<=n;i++) pre[a[i]]=0;}return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的2016中国大学生程序设计竞赛（长春）Sequence II HDU - 5919 主席树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。