科丁乐LV4分治单元测试题目与讲解

科丁乐LV4分治单元测试题目与讲解

开场白

这次考试真的是很尴尬呀。。。
这个分数简直。。。让人。。。
不可思议。。。

只考了56.5分。。。

第一题

填空1：l<r
填空2：a[m]==x
填空3：m
填空4：r=m
填空5：l=m+1
填空6：-1

第二题

填空1：1%n
填空2：a,b/2,n
填空3：ans=ans*a%n

第三题

填空1：l<r-1
填空2：i<m&&j<r
填空3：num+=m-i
填空4：t[k++]=a[i++]
填空5：t[k++]=a[j++]

第四题

1. K12658 摆火柴 (20分)
题目描述
小科有一盒超级火柴，装有n根火柴，他想把火柴拿出来摆成一行，摆完后火柴是按照高度是从低到高摆放的。每根火柴都有一个高度，现在他想通过交换相邻的两根火柴来完成这个摆放，请问他最少需要交换多少次就能完成火柴的摆放。输入格式
第一行一个整数n，表示火柴的数量 n≤5*10^5第二行n个数表示每根火柴的高度 每个火柴的高度≤10^9输出格式
输出一个整数，表示最少需要交换多少次能够完成火柴的摆放输入输出样列
输入样例1：
4
2 1 4 3
输出样例1：
2输入样例2：
5
9 1 0 5 4
输出样例2：
6【耗时限制】1000ms 【内存限制】128MB

这道题就是求逆序对
很简单
然鹅。。。

答题结果：60分

。。。
无语ing…
我们先来分析一下这道题
（没啥好分析的）
求一下逆序对就行了。
我的代码思路正确
可细节错了 数组定义小了 ：

#include<bits/stdc++.h>
using namespace std;
const int N=100001;//数组定义小了啊喂！
int a[N],t[N];

题目里n是5*10^5。。。
正确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000001;//个人习惯
int a[N],t[N];
long long solve(int *a,int l,int r,int *t){long long num=0;if(l<r-1){int m=(l+r)/2;num+=solve(a,l,m,t);num+=solve(a,m,r,t);int i=l,j=m,k=l;while(i<m&&j<r){if(a[i]>a[j]){num+=m-i;t[k++]=a[j++];}else t[k++]=a[i++];}while(i<m) t[k++]=a[i++];while(j<r) t[k++