T1 弱点(weakness.cpp 2S 256M)
-
题面:
题目描述
一队勇士正在向你进攻，每名勇士都有一个战斗值\(a_i\)。但是这队勇士却有一个致命弱点，如果存在\(i<j<k\)使得\(a_i>a_j>a_k\)，则会影响他们整体的战斗力。我们将这样的一组\((i,j,k)\)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。
输入格式
输入的第一行是一个整数\(n\)，表示勇士的数目。
接下来一行包括\(n\)个整数，表示每个勇士的战斗值\(a_i\)。
输出格式
输出为一行，包含一个整数。表示这队勇士的弱点数目。
样例输入
4
10 8 3 1
样例输出
4
数据范围
对于30%的数据，\(3 \le n \le 100\)
对于100%的数据，\(3 \le n \le 1000000\)
对于100%的数据，\(1 \le a_i \le 1000000\)，每个\(a_i\)均不相同
-
解析:
逆序对咋求都记不到了
考试的时候yy了30min，幸好之前看过权值线段树类比了一下不然就挂了（
这玩意也许叫二重逆序对？
一边扫一边在值域内建立第一个树状数组，统计值出现的次数
然后用值域上界的次数前缀和减去要求的数的前缀和就是在它之前比它大的数的数量.
然后对逆序对个数再建立第二个树状数组，求得在 \(x\) 之前比它大的数的逆序对个数和.
记得先求出值域上界.
哦对了，以后开#define int long long不要过于小心了
如果稳不炸空间直接开就行
这题 \(10\;pts\) 需要long long.（ ull是改错的时候直接淦上去的
-
code:
#include <bits/stdc++.h>
#define ri register int
#define MAXN 1000015
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template<typename T>
#define lowbit(x) ((x)&(-x))
#define ull unsigned long long
#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
namespace SlowIO
{
Tp inline void rd(T &x) {
x=0;char i=g();bool f=1;
while(!isdigit(i)) f&=(i!='-'),i=g();
while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
x*=((f<<1)-1);
}
Tp inline void op(T x){
if(x<0) pc('-'),x=-x;
if(x>=10) op(x/10);
pc(x%10+48);
}
Tp inline void writeln(T x){op(x);pc('\n');}
Tp inline void writesp(T x){op(x);pc(' ');}
}; using namespace SlowIO;
int n,a[MAXN];
int maxx=0;
ull tr[MAXN],tot;
inline void change(int x,int d){
while(x<=maxx) tr[x]+=d,x+=lowbit(x);
}
inline ull query(int x){
ull ret=0;
while(x) ret+=tr[x],x-=lowbit(x);
return ret;
}
int tr2[MAXN];
inline void change2(int x,int d){
while(x<=maxx) tr2[x]+=d,x+=lowbit(x);
}
inline ull query2(int x){
ull ret=0;
while(x) ret+=tr2[x],x-=lowbit(x);
return ret;
}
signed main()
{
rd(n); for(ri i=1;i<=n;i++) rd(a[i]),maxx=max(maxx,a[i]);
for(ri i=1;i<=n;i++){
change(a[i],1);
change2(a[i],query(maxx)-query(a[i]));
tot+=query2(maxx)-query2(a[i]);
}
op(tot);
return 0;
}
T2 滑动的窗户(window.cpp 3S 256M)
蝉蜩队列板子
T3 操作系统(system.cpp 2S 256M)
-
题面:
题目描述
写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。如果一个进程到达时，CPU正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。一旦CPU空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。
输入格式
输入文件包含若干行，每一行有四个自然数（均不超过\(10^8\)），分别是进程号，到达时间，执行时间和优先级。不同进程有不同的编号，不会有两个相同优先级的进程同时到达。输入数据已经按到达时间从小到大排序。输入数据保证在任何时候，等待队列中的进程不超过\(15000\)个。
输出格式
按照进程结束的时间输出每个进程的进程号和结束时间。
样例输入
1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4
样例输出
1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42
数据范围
进程总数 \(\le 500000\)
-
解析
直接模拟
以后遇到这种要注意数据的单调性，谨防出现CSP-S R2T1的申必错误（
并且要注意模拟的方式，不要直接上纯抱粒，模拟也可以优化
T4 阿Q的停车场(park.cpp 1S 256M)
-
题面:
题目描述
刚拿到驾照的 KJ 总喜欢开着车到处兜风，玩完了再把车停到阿 Q 的停车场里，虽然她对自己停车的水平很有信心，但她还是不放心其他人的停车水平，尤其是 Kelukin。于是，她每次都把自己的爱车停在距离其它车最远的一个车位。KJ 觉得自己这样的策略非常科学，于是她开始想：在一个停车场中有一排车位，从左到右编号为 \(1\) 到 \(n\)，初始时全部是空的。有若干汽车，进出停车场共 \(m\) 次。对于每辆进入停车场的汽车，会选择与其它车距离最小值最大的一个车位，若有多个符合条件，选择最左边一个。KJ 想着想着就睡着了， 在她一旁的 Kelukin 想帮她完成这个心愿，但是他又非常的懒，不愿意自己动手，于是就把这个问题就留给了你：在 KJ 理想的阿 Q 的停车场中，给你车辆进出的操作序列，依次输出每辆车的车位编号。
输入格式
第一行，两个整数 \(n\) 和 \(m\)，表示停车场大小和操作数；
接下来 \(m\) 行，每行两个整数 \(F\) 和 \(x\)
F 是 1 表示编号为 \(x\) 的车进停车场；
F 是 2 表示编号为 \(x\) 的车出停车场；
保证操作合法，即：
出停车场的车一定目前仍在停车场里；
停车场内的车不会超过 \(n\)；
输出格式
对于所有操作 1，输出一个整数，表示该车车位的编号。
样例输入
7 11
1 15
1 123123
1 3
1 5
2 123123
2 15
1 21
2 3
1 6
1 7
1 8
样例输出
1
7
4
2
7
4
1
3
数据范围
对 30%的数据 \(n \le 1000\) ，\(m \le 1000\)
对 60%的数据 \(n \le 200000\)，\(m \le 2000\)
对 100%的数据 \(n,m \le 200000\)，车的编号小于等于 \(10^6\)
-
解析:
考试的时候用单调栈打了个 \(O(nm)\) 的抱粒
左右求第一个更大的数，然后抱粒更新最优位置
它长这样:
#include <bits/stdc++.h>
#define ri register int
#define MAXN 200005
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template<typename T>
using namespace std;
const int inf=0x3f3f3f3f;
namespace SlowIO
{
Tp inline void rd(T &x) {
x=0;char i=g();bool f=1;
while(!isdigit(i)) f&=(i!='-'),i=g();
while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
x*=((f<<1)-1);
}
Tp inline void op(T x){
if(x<0) pc('-'),x=-x;
if(x>=10) op(x/10);
pc(x%10+48);
}
Tp inline void writeln(T x){op(x);pc('\n');}
Tp inline void writesp(T x){op(x);pc(' ');}
}; using namespace SlowIO;
int n,m,a[MAXN],in[MAXN];
int l[MAXN],r[MAXN],dist[MAXN],temp;
stack<int> sta,sta2;
inline void update(){
memset(dist,0,sizeof(dist));
while(!sta.empty()) sta.pop();
while(!sta2.empty()) sta2.pop();
for(ri i=1;i<=n;i++){
while(!sta.empty()&&a[sta.top()]<=a[i])
sta.pop();
if(!sta.empty()) l[i]=sta.top();
sta.push(i);
while(!sta2.empty()&&a[sta2.top()]<=a[n-i+1])
sta2.pop();
if(!sta2.empty()) r[n-i+1]=sta2.top();
sta2.push(n-i+1);
}
for(ri i=1;i<=n;i++){
if(a[i]) dist[i]=-inf;
else if(l[i]&&r[i])
dist[i]=min(i-l[i],r[i]-i);
else if(l[i])
dist[i]=i-l[i];
else if(r[i])
dist[i]=r[i]-i;
else dist[i]=inf;
}
}
//O(m)*O(3n)=O(mn)
int main()
{
ri F,x;
rd(n),rd(m);
for(ri i=1;i<=m;i++){
update();
rd(F),rd(x);
if(F&1){
temp=0;
for(ri j=1;j<=n;j++)
if(dist[j]>dist[temp])
temp=j;
in[x]=temp,a[temp]=1;
writeln(temp);
}
else a[in[x]]=0,in[x]=0;
}
return 0;
}
测的时候全部 \(\tt{\color{deeppink}RE}\)，哈哈哈哈，原来它不行.不愧是我.
然而即日便证明是可以了，作证的便是把数组开大之后我就 \(0 \to 30\;pts\)（
这是因为到达的编号是 \(1e6\) 而我老实地照着 \(n\) 的范围开了 \(2e5\)
哈哈，哈哈哈哈哈哈哈哈一次考试因为开小挂了70+
然后讲讲正解
sol说有两个方法，一个线段树一个set
但是线段树是什么啊，好难，我不知道
所以我选红(s)黑(e)树(t)
把区间信息存进结构体维护，在set里装可以停车的区间（其实就是全部为 \(0\) 的区间
因为set可以重载()来实现自定义排序，所以可以维护最优区间
怎么达到题目要求的最优呢？
设定排序关键字如下：
- 1.与最近车的距离，降序
满足题目条件. - 2.区间的左端点，升序
在两个区间距离相等的情况下，在左边的区间更优，因为停车的顺序是优先最左边. - 3.区间长度，降序
哦，sol里说的，但是其实这一条没用，前两个已经足够了而且我也不明白这一条有什么用
那么就可以写出 清新马蜂独特压行的 排序代码了：
struct interval{
int l,r;
inline int dist(){
return ((l==1||r==n)?(r-l+1):((r+l>>1)-l+1)); } //找到区间离最近车的距离 这里尽量自己理解
inline int loc(){ return r+l>>1; } //找到区间里应该停的位置
}val1,val2;
struct operation{
inline bool operator ()(interval a,interval b){
return (a.dist()==b.dist())?(a.l<b.l):(a.dist()>b.dist());
} //第一关键字为距离，第二关键字为左端点
};
set<interval,operation> st;//建立set
然后您会发现，光排个序有个樢用？该不会的还是不会.
怎么办？回归保零？
还有姬绘！
所以就引出了两个绝妙操作：
\[\color{royalblue}{\large\texttt{Separate}} \] \[\color{gold}{\texttt{分裂区间}} \]和
\[\color{royalblue}{\large\texttt{Merge}} \] \[\color{gold}{\texttt{合并区间}} \].oh folk我竟然又把separate打成了seperate
Separate操作：
每次需要停车，就从set中取出最优区间，用结构体里的loc()函数获取最优的停车位，标记停车，然后把这个区间从停车位那里断开变成两个区间，再放回set中等待使用.
Merge操作：
有车要走？那肥肠好，因为又可以多一个空位置.
所以我们就找出这辆车左边和右边的第一辆车，并且把它们三辆车中间的两个区间取出，然后合并成同一个区间放回去.
通过这两个骚操作，再加上set插入时自动排序的牛X功能，我们成功实现了最优区间的维护.
然后你就做完了最难的T4.
感觉这道题大概蓝到低档紫
但考试的时候还是比较难想的
上代码罢，里面有亿点注释
-
code:
#include <bits/stdc++.h>
#define ri register int
#define MAXN 1000005
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template<typename T>
using namespace std;
const int inf=0x3f3f3f3f;
namespace SlowIO
{
Tp inline void rd(T &x) {
x=0;char i=g();bool f=1;
while(!isdigit(i)) f&=(i!='-'),i=g();
while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
x*=((f<<1)-1);
}
Tp inline void op(T x){
if(x<0) pc('-'),x=-x;
if(x>=10) op(x/10);
pc(x%10+48);
}
Tp inline void writeln(T x){op(x);pc('\n');}
Tp inline void writesp(T x){op(x);pc(' ');}
}; using namespace SlowIO;
int n,m,temp;
int in[MAXN]; //in[x]是第x辆车停在了哪个位置
struct interval{
int l,r;
inline int dist(){
return ((l==1||r==n)?(r-l+1):((r+l>>1)-l+1)); } //找到区间离最近车的距离 这里尽量自己理解
inline int loc(){ return r+l>>1; } //找到区间里应该停的位置
}val1,val2;
struct operation{
inline bool operator ()(interval a,interval b){
return (a.dist()==b.dist())?(a.l<b.l):(a.dist()>b.dist());
} //第一关键字为距离，第二关键字为左端点
};
set<interval,operation> st;//建立set
set<int> parked; //第二个set用于维护和快速找到停了车的点
set<int>::iterator locat; //迭代器
inline void Separate(){
temp=val1.loc(),val2=val1;
val1.r=temp-1,val2.l=temp+1; //分裂成两个区间
st.insert(val1),st.insert(val2); //把它们插入set中
}
inline void Merge(int x){
locat=parked.find(in[x]),
--locat; //找到需要修改位置的左边第一个1
val1.l=*locat+1,val1.r=in[x]-1; //制造一个区间
++++locat; //需要修改位置的右边第一个1
val2.l=in[x]+1,val2.r=*locat-1; //制造第二个区间
st.erase(val1); st.erase(val2); //把原本在set中的这两个区间删除，因为要合并
val1.r=val2.r,st.insert(val1); //合并成一个区间，并把它加入set中
parked.erase(in[x]),in[x]=0; //车离开了
}
int main()
{
ri F,x;
rd(n),rd(m);
st.insert({1,n}); //先把代表一整个停车场随便停的区间放入set
parked.insert(0),parked.insert(n+1); //防止Merge函数中找不到左右的车 直接RE
while(m--){
rd(F),rd(x);
if(F&1){ //在这里等价于F==1 在F输入只有奇偶两种值的时候可以用
/* Shimo kitazawa */
val1=*st.begin(); //迭代器是指针 访问元素需要 *
st.erase(val1);
/* 这两句不能写在if外面 因为Merge()操作不需要弹出最优区间 */
if(val1.l==1){
temp=val1.l++;
st.insert(val1); //特判掉车位1和n空闲的情况 因为有它们空着的时候
} else if(val1.r==n){
temp=val1.r--;
st.insert(val1); //最优停车位和其它情况不同
} else Separate(); //如果没有特殊情况就直接开始拆分最优区间并且停车.
in[x]=temp,writeln(temp),parked.insert(in[x]); //记得要在parked里标记停车位置 并记录在in[x]中方便Merge
} else
Merge(x); //F==2 操作是出停车场，合并区间
}
return 0;
}