『树状数组·逆序对』飞fly

2023-10-13 12:38

文章标签 数组树状逆序 fly

本文主要是介绍『树状数组·逆序对』飞fly，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{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.

求第一象限内的所有点的鬼畜值之和.

$\mathrm{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;	
}