Turing Tree HDU - 3333 T7 D24

Turing Tree HDU - 3333 T7 D24

查找区间不同元素和。

思路：

离线做法，将所有询问按r值升序排序。线段树维护区间和，遍历整个数组，到某个元素时，若这个元素之前出现过，将之前出现过的位置值变为0，当前位置值设为元素值。查询时区间查询即可

/*
               #########                       
              ############                     
              #############                    
             ##  ###########                   
            ###  ###### #####                  
            ### #######   ####                 
           ###  ########## ####                
          ####  ########### ####               
        #####   ###########  #####             
       ######   ### ########   #####           
       #####   ###   ########   ######         
      ######   ###  ###########   ######       
     ######   #### ##############  ######      
    #######  ##################### #######     
    #######  ##############################    
   #######  ###### ################# #######   
   #######  ###### ###### #########   ######   
   #######    ##  ######   ######     ######   
   #######        ######    #####     #####    
    ######        #####     #####     ####     
     #####        ####      #####     ###      
      #####      ;###        ###      #        
        ##       ####        ####     

       
*/
#include
#include
#include
#include
#include
#include
#define ll long long 
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((t[p].l+t[p].r)>>1) 
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(int x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=2e5+7;
struct Tree{
	ll l,r,cnt,val;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define val(x) t[x].val
}t[qs<<2];
ll T,n,q,A[qs],C[qs],pre[qs];
struct node{
	int l,r,id;
}B[qs];
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	val(p)=0;
	if(l==r) {
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void update(int p,int l,int r,int k){
	if(l<=l(p)&&r>=r(p)){
		val(p)=k;
		return ;
	}
	if(l<=mid) update(ls,l,r,k);
	if(r>mid) update(rs,l,r,k);
	val(p)=val(ls)+val(rs);
}
ll ask(int p,int l,int r){
	if(l<=l(p)&&r>=r(p)) return val(p);
	ll val=0;
	if(l<=mid) val+=ask(ls,l,r);
	if(r>mid) val+=ask(rs,l,r);
	return val;
}
bool cmp(node a,node b){
	if(a.r==b.r) return a.l mp;
int main(){
	T=read();
	while(T--){
		mp.clear();
		n=read();
		for(int i=1;i<=n;++i) {
			A[i]=read();
			pre[i]=mp[A[i]];
			mp[A[i]]=i;
		}
		q=read();
		for(int i=1;i<=q;++i){
			B[i].l=read();
			B[i].r=read();
			B[i].id=i;
		}
		sort(B+1,B+1+q,cmp);
		build(1,1,n);
		int l=1,r=1;
		for(int i=1;i<=q;++i){
			for(;r<=B[i].r;++r) {
				if(pre[r]) update(1,pre[r],pre[r],0);
				update(1,r,r,A[r]);
			}
			ans[B[i].id]=ask(1,1,B[i].r)-ask(1,1,B[i].l-1);
		}
		for(int i=1;i<=q;++i){
			cout<
线段树

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签