题意:
给一个数列,一些询问,问你$[l,r]$之间不同的数字之和
题解:
11年多校的题,现在属于"人尽皆知傻逼题"
核心思想在于: 对于一个询问$[x,R]$ 无论$x$是什么,整个数列中,对于答案有贡献的,只有每种数字中,$R$左边最近的一个
对于数列$1,1,2,2,3,3,4,4,1,1,2,2,4,3,4,5,5,P...$和
$0,0,0,0,0,0,0,0,0,1,0,2,0,3,4,0,5,P...$ 只要右边界保持在P-1,询问结果是等价的
具体操作就是,存储询问,按R排序,依次处理,删除当前询问R之前所有的,只保存最后一个
用线段树,树状数组都行,做单点修改区间查询就行..
bit
#include <bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pp pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)
#define per(ii,a,b) for(int ii=a;ii>=b;ii--)
using namespace std;
const int maxn=1e6+10;
const int maxm=1e6*4+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
#define lb(x) x&-x
ll bit[maxn],num[maxn];
void update(int pos,int x){
while(pos<=n){
bit[pos]+=x,pos+=lb(pos);
}
}
ll sum(int pos){
ll ans=0;
while(pos){
ans+=bit[pos],pos-=lb(pos);
}
return ans;
}
ll query(int a,int b){
return sum(b)-sum(a-1);
}
struct node2 {
int l,r,id;
}ask[maxn];
int cmp(node2 a,node2 b){
return a.r<b.r;
}
map<ll,int>pos;
ll ans[maxn];
int main(){
//#define test
#ifdef test
freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
scanf("%d",&casn);
while(casn--){
scanf("%d",&n);
rep(i,1,n) bit[i]=0;
for(int i=1;i<=n;i++){
scanf("%lld",num+i);
update(i,num[i]);
}
pos.clear();
scanf("%d",&k);
int a,b;
for(int i=1;i<=k;i++){
scanf("%d%d",&a,&b);
ask[i]=(node2){a,b,i};
}
sort(ask+1,ask+1+k,cmp);
int r=1;
for(int i=1;i<=k;i++){
while(r<=ask[i].r){
if(pos[num[r]]){
update(pos[num[r]],-num[r]);
}
pos[num[r]]=r;
r++;
}
ans[ask[i].id]=query(ask[i].l,ask[i].r);
}
for(int i=1;i<=k;i++){
printf("%lld\n",ans[i]);
}
} #ifdef test
fclose(stdin);fclose(stdout);system("out.txt");
#endif
return 0;
}
线段树
#include <bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pp pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)
#define per(ii,a,b) for(int ii=a;ii>=b;ii--)
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
#define nd lst[now]
struct node {
int l,r;ll sum;
}lst[maxm];
ll num[maxn];
void maketree(int s=1,int t=n,int now=1){
nd=(node){s,t,num[s]};
if(s==t) return ;
maketree(s,(s+t)>>1,now<<1);
maketree(((s+t)>>1)+1,t,now<<1|1);
nd.sum=lst[now<<1].sum+lst[now<<1|1].sum;
}
inline void pushup(int now) {
nd.sum=lst[now<<1].sum+lst[now<<1|1].sum;
}
void update(int pos,int x,int now=1){
if(pos<nd.l||pos>nd.r) return ;
if(nd.r==nd.l){
nd.sum=x;
return;
}
update(pos,x,now<<1);
update(pos,x,now<<1|1);
pushup(now);
}
ll query(int s,int t,int now=1){
if(s>nd.r||t<nd.l) return 0;
if(s<=nd.l&&t>=nd.r) return nd.sum;
return query(s,t,now<<1)+query(s,t,now<<1|1);
}
struct node2 {
int l,r,id;
}ask[maxn];
int cmp(node2 a,node2 b){
return a.r<b.r;
}
map<ll,int>pos;
ll ans[maxn];
int main(){
#define test123
#ifdef test
freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endif
scanf("%d",&casn);
while(casn--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",num+i);
}
pos.clear();
maketree();
scanf("%d",&k);
int a,b;
for(int i=1;i<=k;i++){
scanf("%d%d",&a,&b);
ask[i]=(node2){a,b,i};
}
sort(ask+1,ask+1+k,cmp);
int r=1;
for(int i=1;i<=k;i++){
while(r<=ask[i].r){
if(pos[num[r]]){
update(pos[num[r]],0);
}
pos[num[r]]=r;
r++;
}
ans[ask[i].id]=query(ask[i].l,ask[i].r);
}
for(int i=1;i<=k;i++){
printf("%lld\n",ans[i]);
}
} #ifdef test
fclose(stdin);fclose(stdout);system("out.txt");
#endif
return 0;
}