CF Gym 100463A (树状数组求逆序数)
2024-09-29 23:27:50
题意:给你一个序列,和标准序列连线,求交点数。
题解:就是求逆序对个数,用树状数组优化就行了。具体过程就是按照顺序往树状数组了插点(根据点的大小),因为第i大的点应该排在第i位,插进去的时候他前面本该是有i-1个点的,如果少了,那么一定就和这个元素构成了逆序对。
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstring> using namespace std; //#define local
typedef long long ll;
const int maxn = +;
#define lowbit(x) ((x)&-(x))
ll C[maxn];
ll n,a,b;
void add(ll x,ll d)
{
while(x <= n) {
C[x]+=d; x+=lowbit(x);
}
} ll sum(ll x)
{
ll ret = ;
while(x > ){
ret += C[x]; x-=lowbit(x);
}
return ret;
} ll Count()
{
ll res = ;
ll ele = b;
for(int i = ; i < n; i++){
ll pre = sum(ele+);
res += ele - pre;
add(ele+,);
ele = (ele+a)%n;
}
return res;
} int main()
{
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif // local
int cas = ;
while(~scanf("%I64d%I64d%I64d",&n,&a,&b)&&n){
memset(C,,sizeof(C));
printf("Case %d: %I64d\n",++cas,Count());
} return ;
}
最新文章
- Effective C++ -----条款33:避免遮掩继承而来的名称
- SNF开发平台WinForm之四-开发-主细表管理页面-SNF快速开发平台3.3-Spring.Net.Framework
- WCF 扩展一:格式化Web服务请求XML
- CSS3中渐变gradient详解
- Good practice release jar to Nexus
- EF的四种开发模式
- 程序点滴001_Python模拟点阵数字
- 谈一谈applet踩过的坑
- Java进程和线程关系及区别
- Echars鼠标点击事件多次触发
- bzoj1531: [POI2005]Bank notes(多重背包)
- 雷林鹏分享:jQuery EasyUI 表单 - 创建树形下拉框
- Flask系列07--Flask中的CBV, 蓝图的CBV
- (转载)How browsers work--Behind the scenes of modern web browsers (前端必读)
- LeetCode--226--翻转二叉树
- scala sparseVetor, SprseMatrix 实现
- ubuntu系统:插入优盘read-only file system
- asp.net状态保持
- Python 开发
- 关于Koala 中文编译出错
热门文章
- C# 移除string[] 数组中的指定元素
- 在windwo server2008服务器上配置ftp服务器、及配置phpstrom工具、实现项目同步。
- HTML5学习笔记(二)新元素和功能
- 网络编程demo之Udp和URL
- unity3d各种OpenFileDialog操作
- String,StringBuffer和StringBuilder
- CodeForces - 361A-Levko and Table (思维)
- Function.prototype.apply.call
- (转)Nginx的https配置记录以及http强制跳转到https的方法梳理
- 牛客网Java刷题知识点之关键字static、static成员变量、static成员方法、static代码块和static内部类