【SDUTOJ 3323】 园艺问题 (离散化+线段树+离线数据处理)
园艺问题
Time Limit: 1000ms?? Memory limit: 65536K??有疑问?点这里^_^
题目描述
本巨养了一盆双色茉莉。这种花有一种特点:第i朵花在第Di天盛开,刚开时是紫色的,Ai天之后会变成白色,再过Bi天就会凋谢。如Di?=?3,Ai?=?4,Bi?=?5,那么在第3至6天为紫色,第7至11天为白色,第11天之后就凋谢了。
?
现在给出一些事件,你需要按要求给出答案。
事件1:在第Di天开了一朵花,这朵花Ai天后变成白色,再过Bi天就会凋谢。
事件2:询问在第X天时,紫色花朵和白色花朵各有多少。
输入
?
输入包含多组。对于每组数据:
第一行包含一个整数n?(1?<=?n?<=?300,000)。
接下来的n行,为下述两种格式的一种,分别代表事件1和事件2。
1?Di?Ai?Bi
2?X
?
对于所有数据有:1?<=?Di,Ai,Bi?<=?1,000,000?,1?<=?Ai?<=?3,000;
输出
?
对于每个事件2输出一行,包含两个整数代表答案。
示例输入
4
1 3 2 3
2 4
1 2 1 1
2 10
示例输出
由题目可知有两种输入
1 d a b 表示第 [d,d+a-1]天开紫花 [d+a][d+a+b-1]开白花
2 x 询问第x天几紫几白
很容易想到线段树 但10^9太大 一共300000组区间 也就是最多1200000个端点 离散后叶子最多只需1200000即可 这样把所有数据先存起来 然后离线处理 先把区间端点全存起来然后从小到大排序 重标号 建一个足够的线段树 然后读到1就树上处理即可 2就树上查询 注意由于没存x 所以查询的不一定是查到x叶子 可能是包含x的一个最小区间的左端或右端 但不影响
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef struct Node Node;
typedef struct Range Range;
struct Node//线段树
{
int z,b;//节点紫花白花
};
struct Range//存数据
{
int p,x,a,b,c,d;//p-1或2 1:[a,b] [c,d] 2:x
};
map <int,int> hs;//重标号哈希
int pt[1200012];//重标号
Node tr[4800048];//线段树
Range rg[300003];//预存数据离散处理
int tp;//重标号结点数
void SetTree(int site,int l,int r)//建空树
{
if(l == r)
{
tr[site].z = tr[site].b = 0;
return;
}
int mid = (l+r)>>1;
SetTree(site<<1,l,mid);
SetTree(site<<1|1,mid+1,r);
tr[site].b = tr[site].z = 0;
}
void Add(int site,int r,int ll,int rr,int z,int b)//更新树
{
if(l == ll && r == rr)
{
tr[site].z += z;
tr[site].b += b;
//printf("%d %d z%d b%dn",r,tr[site].z,tr[site].b);
return;
}
int mid = (l+r)>>1;
if(mid >= rr) Add(site<<1,mid,ll,rr,z,b);
else if(mid < ll) Add(site<<1|1,b);
else
{
Add(site<<1,b);
Add(site<<1|1,b);
}
}
void Search(int site,int x)//查值
{
if(l == r)
{
printf("%d %dn",tr[site].b);
return;
}
int mid = (l+r)>>1;
tr[site<<1].z += tr[site].z;
tr[site<<1].b += tr[site].b;
tr[site<<1|1].z += tr[site].z;
tr[site<<1|1].b += tr[site].b;
tr[site].z = tr[site].b = 0;
if(pt[mid] >= x) Search(site<<1,x);
else Search(site<<1|1,x);
}
int main()
{
int n,i,j;
while(~scanf("%d",&n))
{
hs.clear();
tp = 0;
for(i = 0; i < n; ++i)
{
scanf("%d",&rg[i].p);
if(rg[i].p == 2)
{
scanf("%d",&rg[i].x);
}
else
{
scanf("%d %d %d",&rg[i].a,&a,&b);
rg[i].b = rg[i].a+a-1;
rg[i].c = rg[i].b+1;
rg[i].d = rg[i].b+b;
//[a,b] = [d,d+a-1] 紫花 [c,d] [d+a,d+a+b-1] 白花
pt[tp++] = rg[i].a;
pt[tp++] = rg[i].b;
pt[tp++] = rg[i].c;
pt[tp++] = rg[i].d;
}
}
sort(pt,pt+tp);
for(i = -1,j = 0; j < tp; ++j)//去重
{
if(i != -1 && pt[j] == pt[i]) continue;
pt[++i] = pt[j];
hs[pt[i]] = i;
}
tp = i;
//for(i = 0; i <= tp; ++i) printf("%d %dn",pt[i],hs[pt[i]]);
SetTree(1,tp);
for(i = 0; i < n; ++i)
{
if(rg[i].p == 1)
{
//printf("%d:%d %d:%d %d:%d %d:%dn",rg[i].a,hs[rg[i].a],rg[i].b,hs[rg[i].b],rg[i].c,hs[rg[i].c],rg[i].d,hs[rg[i].d]);
Add(1,tp,1,0);//[a,b] 紫花++
Add(1,hs[rg[i].d],1);//[c,d] 白花++
}
else
{
if(rg[i].x > pt[tp] || rg[i].x < pt[0]) puts("0 0");//由于x查到左右端点 可能查出范围 特判一下
else Search(1,rg[i].x);
}
}
}
return 0;
}
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|