[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=60083619
向大(hei)佬(e)勢力學(di)習(tou)

前段時間做了一套大佬自己出的題（大佬竟然是個宅男2333），蒟蒻的我自然是只得了30分的暴力分:-(

fleet

艦隊

【題目描述】
艦隊里的每位艦娘都有一個編號i，也有一個類型ti，例如驅逐艦、輕巡洋
艦、航空母艦……
每次提督都想知道從第l 位艦娘到第r 位艦娘中（包含l、r），一共有多
少不同的類型。請你回答他的詢問。
【輸入格式】
第一行一個整數n，表示艦娘數量。
第二行n 個整數，第i 個整數ti 表示艦娘i 的類型。
第三行一個整數q，表示提督的詢問數量。
接下來q 行，每行2 個整數l,r，表示詢問[l,r]有多少不同類型的艦娘。
為了模擬真實情況，本題強制在線。你需要記錄上一次的答案lastans（初
始值為0），每次詢問真實的l,r 為l xor lastans 與r xor lastans，其中xor
表示按位異或操作。
【輸出格式】
輸出q 行，每行一個整數表示詢問的答案。
【樣例數據】
fleet.in
5
1 1 2 1 3
3
1 5
1 7
1 7
fleet.out
3
2
3
【數據范圍】
對于30%的數據，n,q≤5000。
對于另30%的數據，ti≤100000。
對于100%的數據，1≤n,q≤200000，1≤l≤r≤n，1≤ti≤10^9。

正解當然不是我想出來的，而是另一個大佬自己yy出來的

我們建的線段樹表示原序列中出現的不同的數的個數，就是對原序列建樹，只不過對于節點i的線段樹表示1~i區間出現的不同數的個數。
建樹的時候需要記錄這一個數上一次出現的位置，新建一棵樹的時候既要加，又要減。
查詢的時候利用前綴和區間查詢即可
注意要離散化
然后就沒更多的技巧了，但是將這一模型抽出來著實很厲害

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int N=200000+5;struct Node {Node *ls,*rs;int sum;void update(){sum=ls->sum+rs->sum;}
}*root[N],*null,pool[N*40],*tail=pool;
struct tt{int ty,nu;
}t[N];
int n,pre[N];bool cmp1(tt a,tt b){return a.ty<b.ty;
}
bool cmp2(tt a,tt b){return a.nu<b.nu;
}
Node *newnode(){Node *nd=++tail;nd->ls=nd->rs=null;nd->sum=0;return nd;
}
Node *build(int le,int ri){Node *nd=newnode();if(le==ri) return nd;int mid=(le+ri)>>1;nd->ls=build(le,mid);nd->rs=build(mid+1,ri);
}
void insert(Node *&ndn,Node *ndp,int le,int ri,int pos,int val){ndn=newnode();ndn->sum=ndp->sum+val;ndn->ls=ndp->ls,ndn->rs=ndp->rs;if(le==ri) return ;int mid=(le+ri)>>1;if(pos<=mid) insert(ndn->ls,ndp->ls,le,mid,pos,val);else insert(ndn->rs,ndp->rs,mid+1,ri,pos,val);
}
int query(Node *nd,int le,int ri,int L,int R){if(L<=le&&ri<=R){//printf("eh ");return nd->sum;}int mid=(le+ri)>>1;int rt=0;if(L<=mid) rt+=query(nd->ls,le,mid,L,R);if(mid<R) rt+=query(nd->rs,mid+1,ri,L,R);return rt;
}
int main(){freopen("fleet.in","r",stdin);freopen("fleet.out","w",stdout);null=++tail;null->ls=null->rs=null;null->sum=0;scanf("%d",&n);root[0]=build(1,n);for(int i=1;i<=n;i++){scanf("%d",&t[i].ty);t[i].nu=i;}sort(t+1,t+n+1,cmp1);int sz=0,tmp=0;for(int i=1;i<=n;i++){if(tmp!=t[i].ty){tmp=t[i].ty;sz++;t[i].ty=sz;}else t[i].ty=sz;}sort(t+1,t+n+1,cmp2);tmp=0;for(int i=1;i<=n;i++){insert(root[i],root[i-1],1,n,i,1);if(pre[t[i].ty]){//printf("he ");tmp=pre[t[i].ty];insert(root[i],root[i],1,n,tmp,-1);} pre[t[i].ty]=i;}int q,l,r,ans=0;scanf("%d",&q);while(q--){scanf("%d%d",&l,&r);l^=ans;r^=ans;ans=query(root[r],1,n,l,r);printf("%d\n",ans);}return 0;
}

總結：
1、遇到區間的詢問的題說不定就是主席樹
2、如何靈活地運用線段樹也是一大技巧，線段樹可沒有這么簡單，高深著呢！

轉載于:https://www.cnblogs.com/LinnBlanc/p/7763153.html

總結

以上是生活随笔為你收集整理的可持久化线段树（主席树）【舰娘系列】【自编题】的全部內容，希望文章能夠幫你解決所遇到的問題。

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