题意
sol
挺简单的吧。考虑两个元素什么时候不满足条件
设(a_i)与(a_i + 1)最高的不同位分别为0 1
,显然(s)的这一位必须为(0),否则这一位必须为(1)
剩下的就没有限制条件了
时间复杂度:(nlogn)??????!!!!!!
#include<bits/stdc++.h> using namespace std; const int maxn = 30001; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();} while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a[5][maxn], rak[5][maxn], base = 1; bitset<maxn> b[5][175]; main() { n = read(); base = sqrt(n); for (int i = 1; i <= n; i++) for (int j = 0; j < 5; j++) a[j][i] = read(), rak[j][a[j][i]] = i; for (int j = 0; j < 5; j++) for (int i = 1; i * base <= n; i++) for(int k = 1; k <= i * base; k++) b[j][i].set(rak[j][k]); for (int i = 1; i <= n; i++) { bitset<maxn> tmp, cal; tmp.set(); for(int j = 0; j < 5; j++) { cal.reset(); int now = a[j][i] / base; cal |= b[j][now]; for(int k = now * base + 1; k <= a[j][i]; k++) cal.set(rak[j][k]); tmp &= cal; } printf("%dn", tmp.count() - 1); } }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607117.html