还是先写被卡的做法吧。
节点的区间用了现用现计算卡常过了。
被卡了一上午，难过。
话说有人说我码风有点抽象。
思路
主席树做法。
a[i] 是贝壳序列。
先求出 nxt，即与 a[i] 相同的下一个 a[j] 的下标 j。
用 p114514[i] 记了值为 \(i\) 的数的下标，循环到序列第 \(j\) 个数的时候，先看看有没有存上一个数的下标，存了就用 locp 存一下，然后更新 p114514[i]。
然后对 nxt 建主席树，第 \(i\) 棵树维护一个 01 序列，如果 nxt 在 \(\left[1,i\right]\) 中则标记为 \(0\)，否则为 \(1\)。（就是每个线段树代表的其实是一个区间，如果有两个相同值的数在这个区间内会统计下一个忽略上一个）
修改的时候用 locp 存一下每棵线段树要修改的下标，因为每个数和它上一个相等的数是唯一的，如果要修改每次只会修改一个数，开一个数组即可。
每次查询的时候查 root[r] 这颗树上 \(\left[l,r\right]\) 中 \(1\) 的数量即可，不用担心 \(\left[1,l-1\right]\) 这个区间会扣掉树上的一些数，因为记的是 nxt，所以在 \(\left[l,r\right]\) 上不会出现 \(\left[1,l-1\right]\) 区间的数。
写完之后发现可以优化掉 nxt 数组，所以直接去掉了。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,a[MAXN],tot,locp[MAXN],p114514[MAXN],root[MAXN],m;
struct SegmentTreeNode{
int sum,lson,rson;
}tr[MAXN<<5];
int read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x;
}
namespace sol{
int newnode(){
return ++tot;
}
int buildtree(int l,int r){
int p=newnode();
tr[p].sum=r-l+1;
if(l==r)return p;
#define mid ((l+r)>>1)
tr[p].lson=buildtree(l,mid);
tr[p].rson=buildtree(mid+1,r);
#undef mid
return p;
}
void change(int p1,int &p2,int loc,int l,int r){
p2=newnode();
tr[p2].sum=tr[p1].sum-1;
if(l==r)return;
#define mid ((l+r)>>1)
if(loc<=mid){
change(tr[p1].lson,tr[p2].lson,loc,l,mid);
tr[p2].rson=tr[p1].rson;
}else{
tr[p2].lson=tr[p1].lson;
change(tr[p1].rson,tr[p2].rson,loc,mid+1,r);
}
#undef mid
}
int query(int p,int l,int r,int l1,int r1){
if(l1==l&&r1==r)return tr[p].sum;
#define mid ((l1+r1)>>1)
if(r<=mid)return query(tr[p].lson,l,r,l1,mid);
else if(mid<l)return query(tr[p].rson,l,r,mid+1,r1);
else return query(tr[p].lson,l,mid,l1,mid)+query(tr[p].rson,mid+1,r,mid+1,r1);
#undef mid
}
void solve(){
n=read();
for(int i=1;i<=n;++i){
a[i]=read();
}
root[1]=buildtree(1,n);
for(int i=1;i<=n;++i){
locp[i]=p114514[a[i]];
p114514[a[i]]=i;
}
for(int i=2;i<=n;++i){
root[i]=root[i-1];
if(locp[i]!=0)
change(root[i-1],root[i],locp[i],1,n);
}
m=read();
while(m){
--m;
int l,r;
l=read();r=read();
printf("%d\n",query(root[r],l,r,1,n));
}
}
}
int main(){
sol::solve();
return 0;
}
讨厌卡常啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
标签：nxt,right,int,题解,tr,luogu1972,啊啊啊,MAXN From： https://www.cnblogs.com/LiJoQiao/p/17900760.html