[SDOI2009]HH的项链-树状数组/线段树

时间:2022-03-19 21:24:16

树状数组:

 #include<bits/stdc++.h>
using namespace std;
const int maxn = ;
int id[maxn],tree[maxn],vis[maxn],num[maxn];
int n,m;
struct Tree{
int l,r;
int pos;
};
Tree a[maxn];
int buf[];
inline void read(int &x){
char ch=getchar(); x=;
while(ch<'') ch=getchar();
while(ch>='' && ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
}
inline void write(int x){
if(!x){putchar('');putchar(' ');return;}
register int cnt=;
while(x)buf[++cnt]=(x%)+,x/=;
while(cnt)putchar(buf[cnt--]);
putchar('\n');
}
bool cmp(Tree x,Tree y){
return x.r < y.r;
}
int lowbit(int x){
return x & -x;
}
void add(int x,int now){
while(x <= n){
tree[x] += now;
x += lowbit(x);
}
}
int sum(int n){
int ans = ;
while(n != ){
ans += tree[n];
n -= lowbit(n);
}
return ans;
}
int main(){
read(n);
for(int i = ;i <= n;i++)
read(id[i]);
read(m);
for(int i = ;i <= m;i++){
read(a[i].l);
read(a[i].r);
a[i].pos = i;
}
sort(a+,a++m,cmp);
int next = ;
for(int i = ;i <= m;i++){
for(int j = next;j <= a[i].r;j++){
if(vis[id[j]])
add(vis[id[j]],-);
add(j,);
vis[id[j]] = j;
}
next = a[i].r+;
num[a[i].pos] = sum(a[i].r)-sum(a[i].l-);
}
for(int i = ;i <= m;i++)
write(num[i]);
return ;
}

线段树:

 #include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6+;
struct segment_tree{
int l,r,s,sum;
};
segment_tree ask[maxn<<],tree[maxn<<];
int next[maxn],pre[maxn],a[maxn],x[maxn],n,m;
int buf[];
inline void read(int &x){
char ch=getchar(); x=;
while(ch<'') ch=getchar();
while(ch>='' && ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
}
inline void write(int x){
if(!x){putchar('');putchar(' ');return;}
register int cnt=;
while(x)buf[++cnt]=(x%)+,x/=;
while(cnt)putchar(buf[cnt--]);
putchar('\n');
}
bool cmp1(segment_tree x,segment_tree y){
if (x.l == y.l)return x.r < y.r;
else return x.l < y.l;
}
bool cmp2(segment_tree x,segment_tree y){
return x.s < y.s;
}
inline void pushup(int root){
tree[root].sum = tree[root<<].sum+tree[root<<|].sum;
}
inline void build(int root,int l,int r){
tree[root].l = l;
tree[root].r = r;
if(l == r){
tree[root].sum = a[l];
return;
}
int mid = (l+r)>>;
build(root<<,l,mid);
build(root<<|,mid+,r);
pushup(root);
}
inline void update(int root,int k){
if (tree[root].l == k && tree[root].r == k){
a[k] = ;
tree[root].sum = a[k];
return;
}
int mid = (tree[root].l+tree[root].r)>>;
if(k <= mid)update(root<<,k);
else update(root<<|,k);
pushup(root);
}
inline int query(int root,int l,int r){
if(tree[root].l == l && tree[root].r == r)
return tree[root].sum;
int mid = (tree[root].l+tree[root].r)>>;
if(r <= mid)return query(root<<,l,r);
else
if(l > mid)return query(root<<|,l,r);
else return(query(root<<,l,mid)+query(root<<|,mid+,r));
}
int main(){
read(n);
for(register int i = ;i <= n;i++){
read(x[i]);
next[pre[x[i]]] = i;
if(!pre[x[i]])a[i] = ;
pre[x[i]] = i;
}
build(,,n);
scanf("%d",&m);
for(register int i = ;i <= m;i++){
read(ask[i].l);
read(ask[i].r);
ask[i].s = i;
}
sort(ask+,ask+m+,cmp1);
ask[].l = ;
for(register int i = ;i <= m;i++){
if(ask[i-].l != ask[i].l)
for(register int j = ask[i-].l;j <= ask[i].l-;j++)
if(next[j])update(,next[j]);
ask[i].sum = query(,ask[i].l,ask[i].r);
}
sort(ask+,ask+m+,cmp2);
for(register int i=;i<=m;i++)
write(ask[i].sum);
return ;
}

别问我为什么补贴出来分块做法...

因为没学懂!!!没打出来!!!好不容易打出来,给我超时!!!气死了!!!