涨姿势之区间刷新
TimeLimit:2000MS MemoryLimit:128MB
64-bit integer IO format:%I64d
Problem Description
Value_Dragon是一个有钱人。快过年了，所以他准备发红包。但是他发红包的方式很奇葩。他让n个人排成一排。每次选择1-n中的一段区间[l,r]发，给区间中的每一个人一块钱。就这样发了m次红包。发完后他想知道在[1,n]的子区间中有多少个区间满足以下要求
这个区间得到钱的总数不少于s
这个区间可以被分成两个不相交的子区间且每个子区间得到的钱的总数不小于w
（注：一个区间的子区间包括自己本身)
防坑提醒，长度为1的区间比如[1,1],是不能被拆成两个子区间的
Input
第一行是一个整数T代表数据的组数。
接下来有T组数据
每组数据开头有四个整数，分别代表n m s w
接下来m行，每行是是两个数l,r代表区间[l,r]的左右端点
其中T<=10
n<=10^6，m<=10^5
0<l<=r<=n
0<=w<=s<10^8
Output
对于每组数据输出一行，代表符合要求的区间个数
SampleInput
4
1 0 0 0
1000000 0 0 0
1000000 1 0 0
1 1000000
10 10 20 14
2 10
5 9
5 5
6 8
2 6
9 10
6 7
6 10
4 5
5 7
SampleOutput
0
499999500000
499999500000
8
首先，第一步我们肯定要把发的钱用数组存下来，如果每次输入一个[l,r]就吧l到r数组里的数+1，应该是超时的（我没去试）。
所以我们就得用到新姿势
while(m--)
{
scanf("%d%d",&x,&y);
a[x]++;
a[y+1]--;
}
for(i=1;i<=n;i++)
a[i]=a[i-1]+a[i];
用这个方法可以发的钱存入a数组中；
因为题目有多次使用区间和，所以我们最好用前缀和把前N项和存入sum数组；这个比较简单就不发代码了；
最后就是要思考求出如何满足上面两个条件的区间有多少个；
最开始想的是暴力解；试了一下，自己跑都的跑几十秒；只能想新算法；
因为是两段区间，就有三个顶点；估计是三指针；
因为要遍历，所以第一个指针可以用循环枚举；
我写了一个for循环，用i确定了上界，接着找出满足条件2的最大中界r，最后找到满足条件的最大下界l；
防坑提醒，长度为1的区间比如[1,1],是不能被拆成两个子区间的；最开始忘记考虑这个，样例1都没过；
所以最后只需要加一个判断条件（不具体写了，具体看下面代码理解）；
如果都满足的话，在结果上加上l，因为如果l~r~i满足 从1~l都满足；
下面附上核心代码（sum前缀和，区间和可以用两个前缀和相减）
long long sb=0,l,r;
l=r=1;
for(i=1;i<=n;i++)
{
while(r<i&&sum[i]-sum[r]>=w)///把i当成上界，r为中；先找到满足条件的最大中值
r++;
while(l<r-1&&sum[i]-sum[l]>=s&&sum[r-1]-sum[l]>=w)///找到l的最大值
l++;
if(l<r&&sum[i]-sum[l-1]>=s&&sum[i]-sum[r-1]>=w&&sum[r-1]-sum[l-1]>=w)
sb+=l;///最大的left值满足 1~left都满足 所以加上left
///这里l和r没有重新赋值是因为随着i的增加l和r只会增加或者不变
}
printf("%lld\n",sb);///因为是区间长度和 所以可能会炸int