怎么建设一个自己的电商网站,建设公司加盟,标志在线设计网站,网站制作费用传送门:牛客
题目描述:
HH有一串由各种漂亮的贝壳组成的项链。
HH相信不同的贝壳会带来好运#xff0c;所以每次散步完后#xff0c;他都会随意取出一 段贝壳#xff0c;思考它们所表达的含义。
HH不断地收集新的贝壳#xff0c;因此他的项链变得越来越长。
有一天#…传送门:牛客
题目描述:
HH有一串由各种漂亮的贝壳组成的项链。
HH相信不同的贝壳会带来好运所以每次散步完后他都会随意取出一 段贝壳思考它们所表达的含义。
HH不断地收集新的贝壳因此他的项链变得越来越长。
有一天他突然提出了一 个问题某一段贝壳中包含了多少种不同的贝壳
这个问题很难回答。。。因为项链实在是太长了。于是他只 好求助睿智的你来解决这个问题
输入:
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出:
2
2
4对于本题,我们发现可以进行这样的一个转化.假设我们找出了一个数字前一次出现的地方,用last[]last[]last[]记录,那么对于一个询问区间[l,r][l,r][l,r]来说,此时我们只需要找出区间内有几个数字的lastlastlast值是小于lll即可.那么此时我们需要解决的问题就是: ∑ilrlast[i]l\sum_{il}^{r}{last[i]l}il∑rlast[i]l 这是一个主席树的经典模型,直接套主席树即可解决
对于主席树(可持久化线段树),网上有大量的博客讲解(不乏有详细的),此处就不在赘述了.
但是对于此题来说,比较麻烦的是此时我们又出现了0这样的数字,总所周知,朴素的主席树用的是权值线段树的思想,此时我们是无法维护0的.所以我们需要将所有数字的位置都往后移动一位,也就是将2当做我们的贝壳的开始,此时就可以进行维护了
下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000010
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int last[maxn];
int n,m;
struct PerSegment_tree {int l,r,lnum,rnum,sum;
}tree[maxn5];int cnt0;int RT[maxn];
int build(int l,int r) {int pcnt;tree[p].ll;tree[p].rr;if(lr) return p;int mid(lr)1;tree[p].lnumbuild(l,mid);tree[p].rnumbuild(mid1,r);return p;
}
int update(int pre,int val) {int pcnt;tree[p]tree[pre];tree[p].sum1;if(tree[p].ltree[p].r) return p;int mid(tree[p].ltree[p].r)1;if(valmid) tree[p].lnumupdate(tree[pre].lnum,val);else tree[p].rnumupdate(tree[pre].rnum,val);return p;
}
ll query(int pre,int now,int l,int r,int k) {if(lr) return tree[now].sum-tree[pre].sum;int mid(lr)1;if(kmid) return query(tree[pre].lnum,tree[now].lnum,l,mid,k);else {int stree[tree[now].lnum].sum-tree[tree[pre].lnum].sum;return (ll)squery(tree[pre].rnum,tree[now].rnum,mid1,r,k);}
}
int main() {nread();for(int i1;in1;i) last[i]1;RT[1]build(1,n1);for(int i2;in1;i) {int aread();RT[i]update(RT[i-1],last[a]);last[a]i;}mread();for(int i1;im;i) {int lread(),rread();l;r;printf(%lld\n,query(RT[l-1],RT[r],1,n1,l-1));}return 0;
}
