正文

2015 UESTC 数据结构专题A题 秋实大哥与小朋友 线段树 区间更新，单点查询，离散化

IP云
IP云V管理员/2 阅读
09/29
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

秋实大哥与小朋友

Time Limit: 1 Sec  Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/59

Description

秋实大哥以周济天下，锄强扶弱为己任，他常对天长叹：安得广厦千万间，大庇天下寒士俱欢颜。

所以今天他又在给一群小朋友发糖吃。

他让所有的小朋友排成一行，从左到右标号。在接下去的时间中，他有时会给一段区间的小朋友每人v颗糖，有时会问第x个小朋友手里有几颗糖。

这对于没上过学的孩子来说实在太困难了，所以你看不下去了，请你帮助小朋友回答所有的询问。

Input

第一行包含两个整数n，m，表示小朋友的个数，以及接下来你要处理的操作数。

接下来的m行，每一行表示下面两种操作之一：

0 l r v : 表示秋实大哥给[l,r]这个区间内的小朋友每人v颗糖

1 x : 表示秋实大哥想知道第x个小朋友手里现在有几颗糖

1≤m,v≤100000，1≤l≤r≤n，1≤x≤n，1≤n≤100000000。1≤x≤n，1≤n≤100000000。

Output

对于每一个1 x操作，输出一个整数，表示第x个小朋友手里现在的糖果数目。
 

Sample Input

3 4
0 1 3 1
1 2
0 2 3 3
1 3

Sample Output

1
4

HINT

题意

题解：

灰常简单的一个区间更新＋单点查询问题，但是n比较大！比较大！肿么办？

这位 小彭玉请告诉我，肿么办？
哈，我们先把数读进来，然后排个序，维护个前缀和，或者来个map，就可以离散化啦!
我真是机智呀！

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int N=*;
typedef long long LL;struct node
{
int lft,rht;
LL sum,add;
int mid(){return MID(lft,rht);}
void fun(LL tmp)
{
add+=tmp;
sum+=(rht-lft+)*tmp;
}
};int y[N];struct Segtree
{
node tree[N*];
void relax(int ind)
{
if(tree[ind].add)
{
tree[LL(ind)].fun(tree[ind].add);
tree[RR(ind)].fun(tree[ind].add);
tree[ind].add=;
}
}
void build(int lft,int rht,int ind)
{
tree[ind].lft=lft; tree[ind].rht=rht;
tree[ind].sum=; tree[ind].add=;
if(lft==rht) tree[ind].sum=y[lft];
else
{
int mid=tree[ind].mid();
build(lft,mid,LL(ind));
build(mid+,rht,RR(ind));
tree[ind].sum=tree[LL(ind)].sum+tree[RR(ind)].sum;
}
}
void updata(int st,int ed,int ind,int add)
{
int lft=tree[ind].lft,rht=tree[ind].rht;
if(st<=lft&&rht<=ed) tree[ind].fun(add);
else
{
relax(ind);
int mid=tree[ind].mid();
if(st<=mid) updata(st,ed,LL(ind),add);
if(ed> mid) updata(st,ed,RR(ind),add);
tree[ind].sum=tree[LL(ind)].sum+tree[RR(ind)].sum;
}
}
LL query(int st,int ed,int ind)
{
int lft=tree[ind].lft,rht=tree[ind].rht;
if(st<=lft&&rht<=ed) return tree[ind].sum;
else
{
relax(ind);
int mid=tree[ind].mid();
LL sum1=,sum2=;
if(st<=mid) sum1=query(st,ed,LL(ind));
if(ed> mid) sum2=query(st,ed,RR(ind));
return sum1+sum2;
}
}
}seg;
int kiss[*];
int dow[*];
struct oi
{
int x,y,c,id,ty;
};
oi ans[*];
int tot1,tot2=;
int getid(int x)
{
int l=,r=tot2;
int mid=(l+r)>>;
while(dow[mid]!=x&&dow[l]!=x&&dow[r]!=x)
{
mid=(l+r)>>;
if(dow[mid]>x)
r=mid;
else
l=mid+;
}
if(dow[mid]==x)
return mid;
if(dow[l]==x)
return l;
if(dow[r]==x)
return r;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
char str[];
int a,b,c;
memset(y,,sizeof(y));
seg.build(,*,);
for(int i=;i<m;i++)
{
scanf("%s",str);
if(str[]=='')
{
scanf("%d",&a);
ans[i].x=a,ans[i].y=a,ans[i].c=,ans[i].id=i,ans[i].ty=-;
kiss[tot1++]=a;
}
else
{
scanf("%d%d%d",&a,&b,&c);
ans[i].x=a,ans[i].y=b,ans[i].c=c,ans[i].id=i,ans[i].ty=;
kiss[tot1++]=a;
kiss[tot1++]=b;
}
}
tot2=;
sort(kiss,kiss+tot1);
for(int i=;i<tot1;i++)
if(dow[tot2]!=kiss[i])
dow[++tot2]=kiss[i]; for(int i=;i<m;i++)
{
if(ans[i].ty==-)
{
int x=getid(ans[i].x);
printf("%lld\n",seg.query(x,x,));
}
else
{
int x=getid(ans[i].x),y=getid(ans[i].y),z=ans[i].c;
seg.updata(x,y,,z);
}
}
}
return ;
}