本文主要是介绍『树状数组·逆序对』飞fly，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P r o b l e m \mathrm{Problem} Problem
liu_runda决定提高一下知识水平,于是他去请教郭神.郭神随手就给了liu_runda一道神题,liu_runda并不会做,于是把这个题扔到联考里给高二的做.
郭神有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.
求第一象限内的所有点的鬼畜值之和.
S o l u i t o n \mathrm{Soluiton} Soluiton
很容易将题目转化为逆序对问题，我们思考如何求解逆序对。
由于这里的n很大，我们无法做到每一步都求解逆序对，我们发现x是一个等差数列，那么一定会形成若干个递增的序列。
- 若回到第一个个位置，直接统计逆序对。
- 然后每一次都减去等差数列的个数，即如果原来形成了k个等差数列，那么每一次答案会减少k，脑补一下即可；
代码如下：
#include <cstdio>
#include <iostream>#define int long longusing namespace std;int n, x1, a, P, S[100000+10];void add(int x) {for (int i=x;i<=1e5;i+=i&-i)S[i] ++;return;
}int ask(int x,int res = 0) {for (int i=x;i;i-=i&-i)res += S[i];return res;
}signed main(void)
{freopen("fly.in","r",stdin);freopen("fly.out","w",stdout);cin >> n >> x1 >> a >> P;int x = x1, k = 0, ans = 0, sum = 0; add(x1 + 1);for (int i=2;i<=n;++i){x = (x + a) % P;if (x < a) k ++, ans = i-1-ask(x+1), add(x+1);else if (x > x1) ans -= k;else ans = ans - k + 1;sum += ans;}cout<<sum<<endl;return 0;
}
这篇关于『树状数组·逆序对』飞fly的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
