【SDUTOJ 3323】 园艺问题 (离散化+线段树+离线数据处理)

园艺问题

题目描述

本巨养了一盆双色茉莉。这种花有一种特点：第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,000 ,1 <= Ai <= 3,000,000,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;

};

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 l,int r,int ll,int rr,int z,int b)

{

if(l == ll && r == rr)

{

tr[site].z += z;

tr[site].b += b;

return;

}

int mid = (l+r)>>1;

if(mid >= rr) Add(site<<1,l,mid,ll,rr,z,b);

else if(mid < ll) Add(site<<1|1,mid+1,r,ll,rr,z,b);

else

{

Add(site<<1,l,mid,ll,mid,z,b);

Add(site<<1|1,mid+1,r,mid+1,rr,z,b);

}

}

void Search(int site,int l,int r,int x)

{

if(l == r)

{

printf("%d %dn",tr[site].z,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,l,mid,x);

else Search(site<<1|1,mid+1,r,x);

}

int main()

{

int n,a,b,x,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;

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;

SetTree(1,0,tp);

for(i = 0; i < n; ++i)

{

if(rg[i].p == 1)

{

Add(1,0,tp,hs[rg[i].a],hs[rg[i].b],1,0);

Add(1,0,tp,hs[rg[i].c],hs[rg[i].d],0,1);

}

else

{

if(rg[i].x > pt[tp] || rg[i].x < pt[0]) puts("0 0");

else Search(1,0,tp,rg[i].x);

}

}

}

return 0;

}

相关知识

[HDOJ4325]Flowers（树状数组 离散化）
农业物联网数据处理若干关键技术
京东零售营销选品平台架构设计
花期内花的数目【离散化+前缀和+差分】
[HEOI2012] 树状数组 + 离线预处理 超详解【校队排位赛#12 J】
花匠（最长波浪子序列——DP + 权值线段树）
工业数据治理：全解时序数据处理工具
第二课时平行线分线段成比例定理
【数据建模工具】数据处理算法讲解之主成分分析 大数据行业资讯
ai人脸替换工具离线版教程

网址: 【SDUTOJ 3323】 园艺问题 (离散化+线段树+离线数据处理) https://www.huajiangbk.com/newsview1259413.html