首页 > 代码库 > hdu3333 线段树+离散化+离线处理
hdu3333 线段树+离散化+离线处理
可以先做做3874 哪道题数据小 不用离散化
题意是让询问区间和 出现过多次的只能算一次 很明显的线段树
先对询问区间按右值排序(也可以按左值 其实都一样)并记录输入的顺序(用来按输入的顺序输出) 然后进行跟新和查询 如下
对每一个要跟新的值先判断之前出没出现过 如果出现过就消除之前的 再跟新当前的 并记录位置(此处就是为什么要用到离散化) 如果当前跟新的和查询的右值相同则查询
这样做的原因是消除之前出现过的是不会对当前造成影响(想想为什么) 还有就是跟新比当前右值大的位置就没有意义 具体看代码 还有就是注意__int64
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1) struct node { int L,R,ii; }A[100010]; struct Node { int i; int tt; }B[30010]; int map[30010]; int cmp(node a,node b) { return a.R<b.R; } int cmp1(Node a,Node b) { return a.tt<b.tt; } int cmp2(Node a,Node b) { return a.i<b.i; } __int64 num[4*30010]; int update(int L,int R,int pos,int mark,int k) { if(k>0)num[mark]+=map[k]; else num[mark]-=map[-k]; if(L==R&&L==pos) { return 0; } int mid=(L+R)/2; if(pos<=mid) { update(L,mid,pos,LL(mark),k); } else update(mid+1,R,pos,RR(mark),k); return 0; } __int64 find(int L,int R,int left,int right,int mark) { if(L==left&&R==right) { return num[mark]; } int mid=(L+R)/2; if(right<=mid) { return find(L,mid,left,right,LL(mark)); } else if(left>mid) { return find(mid+1,R,left,right,RR(mark)); } else return find(L,mid,left,mid,LL(mark))+find(mid+1,R,mid+1,right,RR(mark)); } int main() { int T,i,j,n,m,a,b; int leap[30010]; __int64 print[100010]; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&B[i].tt); B[i].i=i; } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&A[i].L,&A[i].R); A[i].ii=i; } memset(num,0,sizeof(num)); sort(B+1,B+1+n,cmp1); sort(A+1,A+1+m,cmp); int k=-1; j=0; for(i=1;i<=n;i++) { if(B[i].tt!=k) { k=B[i].tt; j++; map[j]=k; B[i].tt=j; } else B[i].tt=j; } sort(B+1,B+1+n,cmp2); memset(leap,0,sizeof(leap)); for(i=1,j=1;i<=n&&j<=m;i++) { if(leap[B[i].tt]) update(1,n,leap[B[i].tt],1,-B[i].tt); update(1,n,i,1,B[i].tt); leap[B[i].tt]=i; while(i==A[j].R) { print[A[j].ii]=find(1,n,A[j].L,A[j].R,1); j++; if(j>m) break; } } for(i=1;i<=m;i++) printf("%I64d\n",print[i]); } return 0; }
hdu3333 线段树+离散化+离线处理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。