关于今天模拟赛 T7
2025-08-02 17:41:14
发布于：浙江
29阅读
0回复
0点赞
我直接写了个乱搞代码，最坏时间复杂度是 的，但是跑了不到 1s。这下真是 n 方过五十万了（（（
这个乱搞就是赌他数据随机，已经有人证明过了，在纯随机数据下，期望复杂度为 。
//试试知名乱搞做法
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int val, id;
bool operator < (const node &b) const{
return val < b.val;
}
}a[500005];
int n, m;
inline int read(){
int val = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
val = (val << 3) + (val << 1) + c - '0';
c = getchar();
}
return val;
}
inline void write(int n){
char buf[35];
int ct = 0;
while(n){
buf[++ct] = n % 10 + '0';
n /= 10;
}
for(int i = ct; i; i--) putchar(buf[i]);
}
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
n = read(), m = read();
for(int i = 1; i <= n; i++){
a[i].val = read();
a[i].id = i;
}
stable_sort(a + 1, a + n + 1);
while(m--){
int l = read(), r = read();
for(int i = 1; i <= n; i++){
if(l <= a[i].id && a[i].id <= r){
write(a[i].val), putchar(' ');
break;
}
}
}
return 0;
}
有帮助，赞一个