成段更新加離散化線段樹
這題做了快有一天了。。。。各種問題啊，開始建樹時沒有把查詢的節點加入樹中，結果在查詢時發現很多節點的信息丟失了，糾結了半天去看了下別人的代碼，原來建樹時就應把查詢的節點加入，在做離散化時，將hash數組開到10^9，又超內存了，通不過編譯,囧，之後改成map映射，終於羞愧的A了（這題的數據可能比較弱，不加離散化也能過）
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define N 100005
map<int,int>h;
int x[3*N]; //要加上查詢的節點
int ask[N];
struct cam2
{
int x;
int y;
}flower[N*2];
struct cam1
{
int x;
int y;
int sum;
int add;
}list[N*4];
void build(int k,int x,int y)
{
int mid;
list[k].add=0;
list[k].x=x;
list[k].y=y;
list[k].sum=0;
if(list[k].x==list[k].y)
return;
mid=(x+y)/2;
build(k<<1,x,mid);
build(k<<1|1,mid+1,y);
}
void update(int k,int x,int y,int d)
{
int mid;
if(list[k].x==x&&list[k].y==y)
{
list[k].sum+=(list[k].y-list[k].x+1)*d;
list[k].add+=d;
return;
}
if(list[k].add!=0)
{
list[k<<1].sum+=(list[k<<1].y-list[k<<1].x+1)*list[k].add;
list[k<<1|1].sum+=(list[k<<1|1].y-list[k<<1|1].x+1)*list[k].add;
list[k<<1].add+=list[k].add;
list[k<<1|1].add+=list[k].add;
list[k].add=0;
}
mid=(list[k].x+list[k].y)/2;
if(x>mid)
update(k<<1|1,x,y,d);
else if(y<=mid)
update(k<<1,x,y,d);
else
{
update(k<<1,x,mid,d);
update(k<<1|1,mid+1,y,d);
}
list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
int find(int k,int x,int y)
{
int mid;
if(list[k].x==x&&list[k].y==y)
return list[k].sum;
if(list[k].add!=0)
{
list[k<<1].sum+=(list[k<<1].y-list[k<<1].x+1)*list[k].add;
list[k<<1|1].sum+=(list[k<<1|1].y-list[k<<1|1].x+1)*list[k].add;
list[k<<1].add+=list[k].add;
list[k<<1|1].add+=list[k].add;
list[k].add=0;
}
mid=(list[k].x+list[k].y)/2;
if(x>mid)
return find(k<<1|1,x,y);
else if(y<=mid)
return find(k<<1,x,y);
return find(k<<1,x,mid)+find(k<<1|1,mid+1,y);
}
int main()
{
int k,t,n,m,i,cnt,num;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d%d",&n,&m);
cnt=0;
for(i=0;i<n;i++)
{
scanf("%d%d",&flower[i].x,&flower[i].y);
x[cnt++]=flower[i].x;
x[cnt++]=flower[i].y;
}
printf("Case #%d:\n",k);
for(i=0;i<m;i++) //建樹時就將要查詢的節點插入，否則在查詢時會丟失節點信息
{
scanf("%d",&ask[i]);
x[cnt++]=ask[i];
}
sort(x,x+cnt);
cnt=unique(x,x+cnt)-x;
h.clear();
for(i=0;i<cnt;i++) //減小建樹的空間
h[x[i]]=i;
build(1,0,cnt-1);
for(i=n-1;i>=0;i--)
update(1,h[flower[i].x],h[flower[i].y],1);
for(i=0;i<m;i++) www.2cto.com
printf("%d\n",find(1,h[ask[i]],h[ask[i]]));
}
return 0;
}
