洛谷-数据结构2-1-二叉堆与树状数组4
P1908 逆序对
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
Update：数据已加强。
输入格式
第一行，一个数 n，表示序列中有 n 个数。
第二行 n 个数，表示给定的序列。序列中每个数字不超过 109。
输出格式
输出序列中逆序对的数目。
输入输出样例
输入 #1复制
6 5 4 2 6 3 1
输出 #1复制
11
说明/提示
对于 25% 的数据，n≤2500。
对于 50% 的数据，n≤4×104。
对于所有数据，1≤n≤5×105。
应该不会有人 O(n2) 过 50 万吧 —— 2018.8 chen_zhe。
实现代码：
#include<cstdio>
#include<iostream>
using namespace std;
int n,a[500010],c[500010];
long long ans;
void msort(int b,int e)
{
if(b==e)
return;
int mid=(b+e)/2,i=b,j=mid+1,k=b;
msort(b,mid),msort(mid+1,e);
while(i<=mid&&j<=e)
if(a[i]<=a[j])
c[k++]=a[i++];
else
c[k++]=a[j++],ans+=mid-i+1;
while(i<=mid)
c[k++]=a[i++];
while(j<=e)
c[k++]=a[j++];
for(int l=b;l<=e;l++)
a[l]=c[l];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
msort(1,n);
printf("%lld",ans);
return 0;
}
P5677 [GZOI2017] 配对统计
题目背景
GZOI2017 D1T3
题目描述
给定 n 个数 a1,⋯,an。
对于一组配对 (x,y)，若对于所有的 i=1,2,⋯,n，满足 ∣ax−ay∣≤∣ax−ai∣(i=x)，则称 (x,y) 为一组好的配对（∣x∣ 表示 x 的绝对值）。
给出若干询问，每次询问区间 [l,r] 中含有多少组好的配对。
即，取 x,y（l≤x,y≤r 且 x=y），问有多少组 (x,y) 是好的配对。
输入格式
第一行两个正整数 n,m。
第二行 n 个数 a1,⋯,an。
接下来 m 行，每行给出两个数 l,r。
输出格式
Ansi 表示第 i 次询问的答案，输出 i=1∑mAnsi×i 即可。
输入输出样例
输入 #1复制
3 2 2 1 3 1 2 1 3
输出 #1复制
10
说明/提示
【样例解释】
第一次询问好的配对有：(1,2)(2,1)；
第二次询问好的配对有：(1,2)(2,1),(1,3)(3,1)；
答案 =2×1+4×2=10。
【数据约束】
| 数据编号 | n | m | ai |
|---|---|---|---|
| 1 | ≤300 | ≤300 | 1≤ai≤109 |
| 2 | |||
| 3 | ≤5000 | ≤5000 | |
| 4 | |||
| 5 | ≤5×104 | ≤5×104 | |
| 6 | |||
| 7 | |||
| 8 | ≤3×105 | ≤3×105 | |
| 9 | |||
| 10 |
对于 100% 的数据，∀1≤i<j≤n,ai=aj，1≤l≤r≤n。
实现代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
int lowbit(int x){ return x & (-x);}
int n,m;
ll tree[300001];
void add(int pos){
while(pos<=n)
tree[pos]++,pos+=lowbit(pos);
}
int Query(int num){
ll sum=0;
while(num>0)
sum+=tree[num],num-=lowbit(num);
return sum;
}
struct Num{
ll num; int pos;
}a[300001];
bool cmp(Num a1,Num a2){return a1.num<a2.num;}
struct Pair{
int l,r;
}pairr[600002];
int paircnt=0;
void add_pair(Num a1,Num a2){
int l=min(a1.pos,a2.pos) , r=max(a1.pos,a2.pos);
pairr[++paircnt].l=l;
pairr[paircnt].r=r;
return ;
}
bool cmpPair(Pair a1,Pair a2){
if(a1.r!=a2.r) return a1.r<a2.r;
else return a1.l<a2.l;
}
struct Questions{
int l,r,pos;
}question[300001];
bool cmpQestions(Questions a1,Questions a2){
if(a1.r!=a2.r) return a1.r<a2.r;
else return a1.l<a2.l;
}
int main(){
scanf("%d %d",&n,&m);
if(n==1){puts("0");return 0;}
for(int i=1 ; i<=n ; i++){
scanf("%lld",&a[i].num);
a[i].pos=i;
}
sort(a+1,a+1+n,cmp);
add_pair(a[1],a[2]);
add_pair(a[n],a[n-1]);
for(int i=2 ; i<n ; i++){
int ldif = a[i].num-a[i-1].num , rdif = a[i+1].num-a[i].num;
if(ldif<rdif) add_pair(a[i],a[i-1]);
else if(ldif==rdif) add_pair(a[i],a[i-1]),add_pair(a[i],a[i+1]);
else add_pair(a[i],a[i+1]);
}
sort(pairr+1 , pairr+1+paircnt , cmpPair);
for(int i=1;i<=m;i++){
scanf("%d %d", &question[i].l ,&question[i].r);
question[i].pos=i;
}
sort(question+1 , question+1+m , cmpQestions);
ll ans=0;
for(int i=1,j=1 ; i<=m ; i++){
while(pairr[j].r<=question[i].r && j<=paircnt){
add(pairr[j].l);
j++;
}
ans+=1ll * question[i].pos * (j-1- Query(question[i].l-1) );
}
printf("%lld",ans);
return 0;
}
P1966 [NOIP 2013 提高组] 火柴排队
题目背景
NOIP2013 提高组 D1T2
题目描述
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：∑(ai−bi)2。
其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 108−3 取模的结果。
输入格式
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。
输出格式
一个整数，表示最少交换次数对 108−3 取模的结果。
输入输出样例
输入 #1复制
4 2 3 1 4 3 2 1 4
输出 #1复制
1
输入 #2复制
4 1 3 4 2 1 7 2 4
输出 #2复制
2
说明/提示
输入输出样例说明一
最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。
输入输出样例说明二
最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。
数据范围
对于 10% 的数据， 1≤n≤10；
对于 30% 的数据，1≤n≤100；
对于 60% 的数据，1≤n≤103；
对于 100% 的数据，1≤n≤105，0≤ai,bi<231 且对于任意 1≤i<j≤n，ai=aj，bi=bj。
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=99999997;
long long n,x[10000005],p[1000005],ans=0;
struct fire{
int hi,bh;
}l1[1000005],l2[1000005];
bool cmp1(fire a,fire b)
{
return a.hi<b.hi;
}
void msort(int s,int t)
{
if(s==t)return ;
int mid=(s+t)/2;
msort(s,mid);msort(mid+1,t);
int i=s,k=s,j=mid+1;
while(i<=mid && j<=t)
{
if(x[i]<=x[j])
{
p[k]=x[i];
++k;++i;
}
else
{
p[k]=x[j];
++k;++j;
ans=(ans+mid-i+1)%mod;
}
}
while(i<=mid)
{
p[k]=x[i];
++k;++i;
}
while(j<=t)
{
p[k]=x[j];
++k;++j;
}
for(int i=s;i<=t;i++)
{
x[i]=p[i];
}
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%d",&l1[i].hi),l1[i].bh=i;
for(int i=1;i<=n;i++)
scanf("%d",&l2[i].hi),l2[i].bh=i;
sort(l1+1,l1+n+1,cmp1);
sort(l2+1,l2+n+1,cmp1);
for(int i=1;i<=n;i++)
x[l2[i].bh]=l1[i].bh;
msort(1,n);
printf("%lld",ans);
return 0;
}
P2161 [SHOI2009] 会场预约
题目背景
形式化题意：
你需要维护一个在数轴上的线段的集合 S，支持两种操作：
A l r 表示将 S 中所有与线段 [l,r] 相交的线段删去，并将 [l,r] 加入 S 中。
B 查询 S 中的元素数量。
对于 A 操作，每次还需输出删掉的元素个数。
题目描述
PP 大厦有一间空的礼堂，可以为企业或者单位提供会议场地。
这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。
一般来说，如果 PP 大厦方面事先已经接受了一个会场预约（例如从 10 日到 15 日），就不会再接受与之相冲突的预约（例如从 12 日到 17 日）。
不过，有时出于经济利益，PP 大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。 于是，礼堂管理员 QQ 的笔记本上经常记录着这样的信息：（本题中为方便起见，所有的日期都用一个整数表示）例如，如果一个为期 10 天的会议从 90 日开始到 99 日，那么下一个会议最早只能在 100 日开始。（此处前后矛盾，若无法理解请参考形式化描述。）
最近，这个业务的工作量与日俱增，礼堂的管理员 QQ 希望参加 SHTSC 的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作：
A 操作：有一个新的预约是从 start 日到 end 日，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便 QQ 与自己的记录相校对。
B 操作：请你的系统返回当前的仍然有效的预约的总数。
输入格式
第一行一个正整数 n，表示操作个数。
接下来 n 行，每行表示一个操作，都是上面两种中的一个。
输出格式
输出 n 行，每行一个整数，表示对应操作的答案。
输入输出样例
输入 #1复制
6 A 10 15 A 17 19 A 12 17 A 90 99 A 11 12 B
输出 #1复制
0 0 2 0 1 2
说明/提示
【数据范围】
对于 100% 的数据，1≤n≤2×105，1≤l≤r≤105。
实现代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
struct Plan{
int l,r;
bool operator <(const Plan &rhs)const{
return r<rhs.l;
}
};
int T;
set<Plan> s;
int main(){
cin>>T;
while(T--){
char c; scanf(" %c",&c);
if(c=='A'){
int l,r,cnt=0; scanf("%d %d",&l,&r);
Plan tmp=(Plan){l,r};
set<Plan>::iterator it=s.find(tmp);
while(it!=s.end()){
++cnt; s.erase(it);
it=s.find(tmp);
}
s.insert(tmp);
printf("%d\n",cnt);
}
else{
printf("%d\n",s.size());
}
}
return 0;
}
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
6
0- 0
已为社区贡献9条内容
所有评论(0)