作者存档：edward_mj

【题目】

提交文件：road.pas/.cpp

输入文件：road.in

输出文件：road.out

 

我们知道，每天都有成千上万的车辆在高速公路上行驶。如果一辆装有若干吨货物的卡车通过一段高速公路，就会对这段公路造成一定程度的破坏。

整段高速公路有一个初始的耐久度I。如果一辆装有d吨货物的卡车通过一段高速公路，这段公路的耐久度就会减少d。一旦某段公路的耐久度小于或等于0，这段公路就会永久性地毁坏。卡车无法通过已经毁坏的地方。

有两种维护公路的车辆：T1和T2。T1车可以将一段公路的耐久度增加r。T2车可以将一段公路的耐久度小于p的部分修复至p。虽然维护公路的车辆可以通过已经毁坏的部分，但是已经毁坏的地方仍然无法修复。

你的任务是统计一下一共有多少辆卡车可以成功通行。

 

输入格式:

第一行是三个整数N、M和I，表示高速公路的长度为N，有M辆车依次通过，整段高速公路的初始的耐久度为I。

以下M行每行描述一辆车，格式如下：

1 s t d：一辆装有d吨货物的卡车准备通过区间[s,t]。在此之前先检查区间[s,t]是否完好。如果区间[s,t]里面有任何一个地方毁坏了，这辆卡车就会取消整个通行计划；否则这辆卡车就可以成功通过区间[s,t]，即使通过之后会把某些地方毁坏。

2 s t r：一辆T1车通过区间[s,t]，为这段公路的耐久度增加r。

3 s t p：一辆T2车通过区间[s,t]，为这段公路的耐久度修复至p。

其中：1≤N≤100000，1≤M≤100000，1≤I≤1000，1≤s≤t≤N，1≤d≤1000，1≤r≤1000，1≤p≤1000。

 

输出格式：

输出一个数，表示有多少辆卡车可以成功通行。

 

输入样例：

3 5 2

2 1 3 3

3 1 3 4

1 1 2 3

1 2 3 2

1 1 3 1

 

输出样例：

2

 

样例解释：

第3辆卡车无法通过区间[1,3]。因为虽然区间[1,2)和区间(2,3]的耐久度大于0，但是2这个点的耐久度为0，所以卡车无法通过。

【算法分析】
这个题就牛X了。。。至少对我来说。
块状链表嘛，就是把长度为n的整个数列分成sqrt(n)份，那么每份就有sqrt(n)个元素了。
然后维护三个标记。
1、key，表示这个块里最小的一个数是多少。
2、delta，这个块里的整体增值。
3、cc，这个块 < cc的要先变成cc。
4、low，这个块上一次标记清空之后，如果a[i]<=low,那么这个路就爆了。
然后我们设定cc都是在delta之前。那么维护上就有一点技巧了。
如果想不通的话就看程序吧。。。我觉得还是写得挺清晰地
= =
然后线段树的话，对于“重叠的标记”和“重叠标记”之间的合并无法做到。
于是无法完成这个任务。
【CODE】
#include #include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int N=100005;
struct Node{int l,r,key,delta,low,cc;}p[N/100];
int a[N],L;
int n,m,Stw,ans;

void build(){
for (int i=1;i<=n;i++) a[i]=Stw;
L=0;
int part=(int)(sqrt(n));
if (part==0) part=1;
for (int i=1;(i-1)*part+1<=n;i++){
L=i;
p[i].l=(i-1)*part+1;
p[i].r=min(i*part,n);
p[i].key=Stw;
p[i].delta=p[i].low=p[i].cc=0;
}
}

void push(int i){
for (int j=p[i].l;j<=p[i].r;j++){
if (a[j]<=p[i].low){
a[j]=0;
continue;
}
a[j]>?=p[i].cc;
a[j]+=p[i].delta;
}
}

void remake(int i){
p[i].delta=p[i].low=p[i].cc=0;
p[i].key=0x7FFFFFFF;
for (int j=p[i].l;j<=p[i].r;j++)
p[i].key}

void Deal1(int l,int r,int w){
int i,j;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
if (p[i].key<=0) return;
continue;
}
push(i);
remake(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++)
if (a[j]<=0) return;
}
ans++;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
p[i].key-=w;
p[i].delta-=w;
if (p[i].cc+p[i].delta<=0) p[i].low>?=(-p[i].delta);
continue;
}
push(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++) a[j]-=w;
remake(i);
}
}

void Deal2(int l,int r,int w){
int i,j;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
if (p[i].key>0) p[i].key+=w;
p[i].delta+=w;
continue;
}
push(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++)
if (a[j]>0) a[j]+=w;
remake(i);
}
}

void Deal3(int l,int r,int w){
int i,j;
for (i=1;i<=L;i++){
if (r if (l<=p[i].l && p[i].r<=r){
if (p[i].key>0) p[i].key>?=w;
p[i].cc>?=w-p[i].delta;
continue;
}
push(i);
for (j=max(l,p[i].l);j<=min(r,p[i].r);j++)
if (a[j]>0) a[j]>?=w;
remake(i);
}
}

void solve(){
int i,op,l,r,w;
scanf("%d%d%d",&n,&m,&Stw);
build();
ans=0;
for (i=1;i<=m;i++){
scanf("%d%d%d%d",&op,&l,&r,&w);
switch (op){
case 1:
Deal1(l,r,w);
break;
case 2:
Deal2(l,r,w);
break;
case 3:
Deal3(l,r,w);
break;
}
}
printf("%dn",ans);
}

int main(){
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
solve();
}