HDU 3333 & 离线+线段树

题意:

  统计一段区间内不同数字之和.如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]);
}
}
上一篇:spring ehcache 页面、对象缓存


下一篇:JavaScript异步编程__“回调地狱”的一些解决方案