HDU 3333 & 离线+线段树

时间：2022-05-07 10:05:30

题意:

　　统计一段区间内不同数字之和.如1 1 2 3 1 统计2---5即1+2+3.

SOL:

　　很少打过离线的题目...这种可离线可在线的题不管怎么样一般都是强行在线...

　　考虑这题,此前做过一个类似的题----POJ的染色,那个题目因为颜色不多,可以用二进制记录状态水过.而这个题目刚开始没有什么想法...更别说带更改的题目了(不过貌似树套树还挺好写的...).

　　网上的题解都模模糊糊...看了将询问排序就有点醍醐灌顶.

　　没有修改的这样的询问有什么特点与优势呢? 前面的数对后面没有影响-----当我们将询问按照右端点升序排好后,对于当前询问,右端点以右的数对结果没有影响,
我们可以将数列的元素一个一个插入,如果出现两个元素相同,我们只需要保留坐标更靠后的那一个-----正确性是否显然?对于两个相同元素ai,aj,1<=i<j<=n,我们对一个询问(l,r)进行讨论.

由于排序的性质有r>=j. 若l<=i,则没有什么影响,若l>i,若我们不保存j,就不能得到正确答案.

　　因为数据比较大,所以不仅要离散化,数据还要开longlong,也是因此wa了一次.

　　

　　这题过得还是比较轻松,接下来打打修改版的吧...

CODE:

　　

/*==========================================================================

# Last modified: 2016-02-25 14:50

# Filename: hdu3333.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm> 

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector> 

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1] 

#define maxn 200000

#define maxm 200000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull; 

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

struct Infor{

	ll a,id;

}sorta[maxn];

struct Query{

	int ql,qr,id;

}q[maxm];

ll ans[maxn],sum[maxn],num[maxn],L,R,cnt=0,number[maxn],last[maxm];

int cmp1(const Query &x,const Query &y){return x.qr<y.qr;}

int cmp(const Infor &x,const Infor &y){ return x.a<y.a; }

void pushup(int o){ sum[o]=sum[o*2]+sum[o*2+1];}

void updata(int o,int l,int r,int q,ll x){

	if (l==r) {

		sum[o]=x;

		return;

	}

	int mid=rs(l,r),lc=ls(o,0),rc=lc|1;

	if (q<=mid) updata(lc,l,mid,q,x);

	else updata(rc,mid+1,r,q,x);

	pushup(o);

}

ll query(int o,int l,int r){

	if (L<=l && r<=R) return sum[o];

	int mid=rs(l,r),lc=ls(o,0),rc=lc|1;

	ll t=0;

	if (L<=mid) t+=query(lc,l,mid);

	if (R>mid) t+=query(rc,mid+1,r);

	return t;

}

int main(){

	int cas; read(cas);

	while (cas--){

		cnt=1;

		memset(num,0,sizeof(num));

		memset(sum,0,sizeof(sum));

		memset(sorta,0,sizeof(sorta));

		memset(q,0,sizeof(q));

		memset(number,0,sizeof(number));

		memset(last,0,sizeof(last));

		int n; read(n);

		FORP(i,1,n) {

			read(number[i]); sorta[i].a=number[i]; sorta[i].id=i;

		}

		sort(sorta+1,sorta+1+n,cmp);

		ll t=sorta[1].a; num[sorta[1].id]=1;

		FORP(i,2,n) {

			if (sorta[i].a!=t) ++cnt,t=sorta[i].a;

			num[sorta[i].id]=cnt;

		}

		int m; read(m);

		FORP(i,1,m) {read(q[i].ql); read(q[i].qr); q[i].id=i;}

		sort(q+1,q+1+m,cmp1);

		int head=1;

		FORP(i,1,n){

			if (last[num[i]]) updata(1,1,n,last[num[i]],0);

			last[num[i]]=i;

			updata(1,1,n,i,number[i]);

			while (q[head].qr==i) {

				L=q[head].ql; R=q[head].qr;

				ans[q[head].id]=query(1,1,n);

				head++;

			}

		}

		FORP(i,1,m) printf("%lld\n",ans[i]);

	}

}

相关文章