题目链接
题解
莫队维护bitset区间交个数
代码
// luogu-judger-enable-o2
#include<cmath>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1 ; c = getchar(); }
while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
return x * f;
}
const int whattt = 20001;
const int maxn = 100007;
int a[maxn],bel[maxn],b[maxn];
int l1[maxn],r1[maxn],l2[maxn],r2[maxn],l3[maxn],r3[maxn];
int sum[maxn];
int n,m,k;
struct Que {
int l,r,id;
Que(int l = 0,int r = 0,int id = 0) :l (l),r (r),id (id){};
bool operator < (const Que & a) const {
if(bel[l] == bel[a.l]) return r < a.r;
return bel[l] < bel[a.l];
}
} q[33334 * 3 + 7];
std::bitset<100000> F[whattt + 7],f;
bool mark[33334 + 7];
int len;
int cnt[maxn],c[whattt * 3 + 7];
void update(int k,int ty) {
k = a[k]; cnt[k] += ty;
if(ty == 1) f[k + cnt[k] - 2] = 1;
else f[k + cnt[k] - 1] = 0;
}
void solve() {
memset(mark,0,sizeof mark);
memset(cnt,0,sizeof(cnt));
std::sort(q + 1,q + len + 1);
int l = 1,r = 0;
f.reset();
for(int i = 1;i <= len;++ i) {
while(r < q[i].r) update(++ r,1);
while(r > q[i].r) update(r --,-1);
while(l < q[i].l) update(l ++,-1);
while(l > q[i].l) update(-- l,1);
if(mark[q[i].id])F[q[i].id] &= f,c[q[i].id] = F[q[i].id].count();
else F[q[i].id] = f,mark[q[i].id] = 1;
}
}
int main() {
//freopen("xp1.in","r",stdin);
n = read(),m = read();
k = sqrt(n);
for(int i = 1;i <= n;++ i) b[i] = a[i] = read(),bel[i] = (i - 1) / k + 1;
std::sort(b + 1,b + n +1);
len = n;
for(int i = 1;i <= n;++ i) a[i] = std::lower_bound(b + 1,b + len + 1,a[i]) - b;
for(int i = 1;i <= m;i += 1) {
l1[i] = read(),r1[i] = read(),l2[i] = read(),r2[i] = read(),l3[i] = read(),r3[i] = read();
sum[i] = r1[i] - l1[i] + 1 + r2[i] - l2[i] + 1 + r3[i] - l3[i] + 1;
}
for(int i = 1;i <= m;i += whattt) {
len = 0;
for(int j = i;j <= i + whattt - 1; ++ j) {
if(j > m) break;
q[++ len] = Que(l1[j],r1[j],j - i + 1);
q[++ len] = Que(l2[j],r2[j],j - i + 1);
q[++ len] = Que(l3[j],r3[j],j - i + 1);
}
solve();
for(int j = i;j < i + whattt; ++ j) {
if(j > m) break;
printf("%d
",sum[j] - 3 * c[j - i + 1]);
//return 0;
}
}
return 0;
}