达哥的飞（fly）题(树状数组）（非常玄妙）

树状数组）（非常玄妙）"/>

达哥的飞（fly）题(树状数组）（非常玄妙）

郭神有n条位于第一象限内的线段,给出每条线段与x轴和y轴交点的坐标,显然这样就可以唯一确定每一条线段.
n条线段和y轴交点的纵坐标分别为1,2,3,4...n.我们记和y轴交点纵坐标为i的线段和x轴交点的横坐标为x[i]+1,x[i]按这样的方式生成:
x[1]由输入给出.
x[i]=(x[i-1]+a) % mod,2<=i<=n.
即:如果x[3]=4,则与y轴交点纵坐标为3的抛物线,和x轴交点的横坐标为4+1=5.
我们保证给出的n,x[1],a,mod使得所有的x[i]互不相同.
对于第一象限内的所有点(点的横纵坐标可以是任意实数),如果一个点被x条线段经过,它的鬼畜值就是x*(x-1)/2.
求第一象限内的所有点的鬼畜值之和.
【输入格式】
一行4个整数n,x[1],a,mod
【输出格式】
1行一个整数表示鬼畜值之和.
【样例输入1】
5 2 4 7
【样例输出1】
5
【数据范围】
第1,2个测试点,n<=100.
第3,4个测试点,n<=10^5.
第5,6个测试点的数据,a<=10.
第7,8个测试点,x[1]=a.
第9,10个测试点,无特殊限制.
对于全部数据,1<=n<=1e7,1<=a<=1e5,1<=mod<=1e8,a,mod互质,n<mod,给出的n,x[1],a,mod使得所有的x[i]互不相同.
请选手注意,1e7个int类型的变量将占用大约40mb的内存,导致内存超限,本题得0分.

//这道题内存限制32mb....

对于两条线段，线段1与y轴交点为y1,x轴交点为y2.线段2与x轴交点为x2,与y轴交点为y2，

两条线段有交点，必须y1 > y2 && x1 < x2 或者 y1 < y2 && x1 > x2;

纵坐标递增，这样交点个数相当与在x坐标的逆序对数。（树状数组nlogn,可以过40分的样子，开不下啊）。

然而先不考虑mod，并且假设x1 <= a,x1,x2,x3,x4,x5是等差序列，x2 - x1 = a, x3 - x2 = a。

考虑mod,假设第i条线段的横坐标xi是第一个大于mod的横坐标，模了mod以后，变成x1',x1'可能在x1前面,也可能在x1后面.

但是x1'和x1的距离等于x2'和x2的距离。//因为x2' = x1' + a, x2 = x1 + a;

同样后面也是如此。

那么我们可以把mod看成一个值域，被分成了很多个长度a的小区间，每个区间内的x分布情况一样（x指的是没被模过的，被模过1次的，被模过2次....比如0-a这段区间内的x1,x1',x1",和下个区间a - 2a的x2,x2',x2"的分布情况一样。）

那么我们只需要求出1-a区间内比x1'小的x有多少个，就可以知道a - 2a区间比x2'小的x有多少个了。

当我们计算第i条线段（它的横坐标为x1')和它组成逆序对的个数时我们可以用它前面的数-没和它组成逆序对的数的个数。

没和它组成逆序对的数的个数：目前0-a区间内比x1’小的数的个数（用树状数组求出），假设为sum个.

答案也就是i-1-sum.

对于x2'，目前a-2a区间内比x2’小的数的个数也为sum个，那么答案为i-1-sum - 整个0-a区间x的个数。

整个0-a区间的个数为1+1，它被模的次数+1.

也就是对于x2来说，整个0-a区间的个数为1

也就是对于x2‘来说，整个0-a区间的个数为1+1；

也就是对于x2“来说，整个0-a区间的个数为1+2；

对于x3',那么答案为i-1-sum - 整个0-2a区间x的个数(其实就是整个0-a区间x的个数*2）.

但是如果x1没在0-a 咋办啊？

那么我们就不管x1在不在0-a先让x1一直+a,直到第一个大于mod的横坐标出现（假设是第i线段，横坐标为xi），模mod后变为x1',把这个数插入0-a的值域树状数组中，再用上面做法来做。

所以对于x1'答案变成了i-1- （第1条线段到第i-1条线段中横坐标比x1’小的线段数）。

对于x2'，答案也就是i-1-（第1条线段到第i-1条线段中横坐标比x2’小的线段数）- 整个0-a区间x的个数.

对于x3',那么答案为i-1-sum - -（第1条线段到第i-1条线段中横坐标比x3’小的线段数）- 整个0-2a区间x的个数(其实就是整个0-a区间x的个数*2）.

对于x1''答案变成了i-1- （第1条线段到第i-1条线段中横坐标比x1’小的线段数）-sum 。(目前0-a区间内比x1’小的数的个数（用树状数组求出），假设为sum个).

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{x = 0; int f = 0; char c = getchar();while(c < '0' || c > '9'){if(c == '-') f = 1; c = getchar();}while(c >= '0' &&  c <= '9'){x = x *10  + c -'0'; c = getchar();}if(f) x = -x;
}
int num;//第一区间的数。 
int n,a,mod,x,f[400005],cnt,sum;
long long ans;
int qurey(int b)
{int rt = 0;for(int i = b; i; i -= i & -i)   rt += f[i];return rt;
}
void modify(int wei,int val)
{for(int i = wei; i <= a; i += i & -i)  f[i] += val;
}
int main()
{read(n);read(x);read(a);read(mod);int i , diyi = x;for(i = 2;  i <= n; i++) { x += a; if(x >= mod) break;}for( ;i <= n; i++){if(x >= mod){x -= mod; sum = qurey(x + 1); modify(x+1,1); num++; cnt = 1;}int  ha = (x > diyi ? (x - diyi)/a + 1 : 0) + sum + 1ll * num * (cnt - 1); ans = ans + i - 1 - ha;x += a; cnt++;}	cout << ans;return 0;
}