這題如果沒有想到一個關鍵點的話就會很難做
這邊提供在線和離線的作法,兩種作法本質相去不遠。
假設有一序列長這樣:
2 5 3 2 6 3 3 5 1 7
我們考慮R=10的詢問。假設我們站在第10個數字往回看,不妨將序列看成這樣:
0 0 0 1 1 0 1 1 1 1
我們將第一次遇見某數字的地方設成1,其他地方為0。
這樣有什麼好處呢?其實只要得到這個序列,任何以R為結尾的詢問[L,R]都是後綴[L,R]的和,例如L= 5,R=10,答案就是5。這可以用任何一個區間求和資料結構完成。
如果對這個作法沒有什麼直觀的感受,建議反覆閱讀理解一下。
我們就有了一個離線作法:將所有詢問讀入,以R從小到大排序,這樣我們就可以一次回答所有以某個R為右界的詢問了。
時間複雜度:O(NlgN+QlgQ) , QlgQ的由來是sort。
那麼要如何在線呢?我們想要隨時查詢「以序列開頭為左界,以某個R為右界」的線段樹(或BIT),因此我們想要保留以1~n為結尾的線段樹。這不就是持久化最簡單的應用嗎?
所以,對原序列做出持久化線段樹,對於每個詢問[L,R],從root[R]下去獲得L~R的區間和就好了。
有一些細節要注意的,說出來就無趣了,可以直接參考code。(Hint:跟new 有關)
時間複雜度:O(NlgN + QlgN)
在線版本code:
#include<cstdio> #include<new> using namespace std; const int maxn=30000+5; const int maxc=1000000+5; struct Node { Node *lc,*rc; int Sum; void pull() {Sum=(lc?lc->Sum:0)+(rc?rc->Sum:0);} Node() {Sum=0;lc=rc=NULL;} }*root[maxn]; void modify(Node* last,Node*& now,int L,int R,int mx,int mv,int first) { if(first || !now) { if(!last) now=new Node(); else now=new Node(*last); } if(L==R) {now->Sum+=mv;return;} int M=L+(R-L)/2; if(mx<=M) modify(last?last->lc:0,now->lc,L,M,mx,mv,first); else modify(last?last->rc:0,now->rc,M+1,R,mx,mv,first); now->pull(); } int query(Node* now,int L,int R,int ql,int qr) { if(!now) return 0; int M=L+(R-L)/2,ret=0; if(ql<=L && R<=qr) return now->Sum; if(ql<=M) ret+= query(now->lc,L,M,ql,qr); if(qr >M) ret+= query(now->rc,M+1,R,ql,qr); return ret; } int last[maxc]; int main() { int n,Q; scanf("%d",&n); for(int i=1,x;i<=n;i++) { int first=1; scanf("%d",&x); if(last[x]) {modify(root[i-1],root[i],1,maxn,last[x],-1,first);first=0;} modify(root[i-1],root[i],1,maxn,i,1,first); last[x]=i; } scanf("%d",&Q); while(Q--) { int L,R; scanf("%d%d",&L,&R); printf("%d\n",query(root[R],1,maxn,L,R)); } }
離線版本code:
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int maxn=30000+5; const int maxQ=200000+5; const int maxc=1000000+5; int n,Q,a[maxn],last[maxc]; struct Query { int id,L,R; bool operator < (const Query& rhs) const {return R<rhs.R || (R==rhs.R && L<rhs.L);} }qu[maxQ]; int c[maxn]; inline int lowbit(int x) {return x&(-x);} void add(int p,int x) { while(p<=n) { c[p]+=x; p+=lowbit(p); } } int query(int p) { int ret=0; while(p) { ret+=c[p]; p-=lowbit(p); } return ret; } int ans[maxQ]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); scanf("%d",&Q); for(int i=0;i<Q;i++) {qu[i].id=i;scanf("%d%d",&qu[i].L,&qu[i].R);} sort(qu,qu+Q); memset(last,0,sizeof last); memset(c,0,sizeof c); int R=0; for(int i=0;i<Q;i++) { while(R+1<=qu[i].R) { if(last[a[R+1]]) add(last[a[R+1]],-1); add(R+1,1); last[a[R+1]]=R+1; R++; } ans[qu[i].id]=query(qu[i].R)-query(qu[i].L-1); } for(int i=0;i<Q;i++) printf("%d\n",ans[i]); }
沒有留言:
張貼留言