3 条题解
-
3
第一道 Ynoi /se
做法
这道题看起来就像不能用数据结构维护的样子。
考虑 bitset 乱搞。
发现答案为 。
其中 很容易知道,考虑如何维护 。
首先要对数字进行离散化。
但……普通的离散化后的值似乎无法维护。
改一下离散化,令 离散化后的值为 。(其中 为当表达式成立时返回值是 ,不成立则为 )。
那么,设离散化后有两个数 ,满足 ,则 为 且 的数的个数。
假设有一个区间,要加入一个数 ,设其在区间中出现的次数为 ,则可以把 bitset 的第 位改为 。显然这个 不会与其它数重合。
再看题目,不需要修改,这就不是莫队么!
所以最终我们的解法就是 bitset+莫队 了。
不过注意,我们开不下 。
其实只要分三次计算就好啦 qwq。
代码
马蜂较烂,建议格式化后食用。#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();} while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();} return x * f; } const int N = 1e5 + 5, M = 34000; struct Que { int l, r, num; } q[M * 3 + 5]; struct Node { int data, num; inline bool operator < (const Node &x) const { return data < x.data; } } h[N]; bitset <N> ans[M + 5], w; int n, m, tot; int a[N], cnt[N], sum[M + 5]; unordered_map <int, int> b; inline bool cmp1(Que c, Que d) { return c.l < d.l; } inline bool cmp2(Que c, Que d) { return c.r > d.r; } inline void add(int x) { w[x - cnt[x]] = 1; cnt[x]++; } inline void del(int x) { cnt[x]--; w[x - cnt[x]] = 0; } inline void solve() { if (tot >= m) return; int num = 0; for (int i = 1; i <= M && tot < m; i++) { ++tot; sum[i] = 0; q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1; q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1; q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1; } for (int i = 1; i <= num / 3; i++) ans[i].set(); int step = sqrt(num); sort(q + 1, q + num + 1, cmp1); for (int i = 1; i <= num; i += step) { int l = i, r = min(i + step - 1, num); sort(q + l, q + r + 1, cmp2); } int L = 1, R = 0; for (int i = 1; i <= num; i++) { if (R < q[i].l || L > q[i].r) { for (int j = L; j <= R; j++) del(a[j]); L = q[i].l; R = q[i].r; for (int j = L; j <= R; j++) add(a[j]); } else { while (R < q[i].r) add(a[++R]); while (R > q[i].r) del(a[R--]); while (L < q[i].l) del(a[L++]); while (L > q[i].l) add(a[--L]); } ans[q[i].num] &= w; } for (int i = L; i <= R; i++) del(a[i]); for (int i = 1; i <= num / 3; i++) printf("%d\n", sum[i] - 3 * ans[i].count()); } int main() { n = read(); m = read(); for (int i = 1; i <= n; i++) { h[i].data = read(); b[h[i].data]++; h[i].num = i; } sort(h + 1, h + n + 1); int pre = 0, s = 0; for (int i = 1; i <= n; i++) { if (h[i].data == pre) a[h[i].num] = s; else { s += b[h[i].data]; pre = h[i].data; a[h[i].num] = s; } } solve(); solve(); solve(); return 0; }
-
-1
#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();} while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();} return x * f; } const int N = 1e5 + 5, M = 34000; struct Que { int l, r, num; } q[M * 3 + 5]; struct Node { int data, num; inline bool operator < (const Node &x) const { return data < x.data; } } h[N]; bitset <N> ans[M + 5], w; int n, m, tot; int a[N], cnt[N], sum[M + 5]; unordered_map <int, int> b; inline bool cmp1(Que c, Que d) { return c.l < d.l; } inline bool cmp2(Que c, Que d) { return c.r > d.r; } inline void add(int x) { w[x - cnt[x]] = 1; cnt[x]++; } inline void del(int x) { cnt[x]--; w[x - cnt[x]] = 0; } inline void solve() { if (tot >= m) return; int num = 0; for (int i = 1; i <= M && tot < m; i++) { ++tot; sum[i] = 0; q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1; q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1; q[++num].l = read(); q[num].r = read(); q[num].num = i; sum[i] += q[num].r - q[num].l + 1; } for (int i = 1; i <= num / 3; i++) ans[i].set(); int step = sqrt(num); sort(q + 1, q + num + 1, cmp1); for (int i = 1; i <= num; i += step) { int l = i, r = min(i + step - 1, num); sort(q + l, q + r + 1, cmp2); } int L = 1, R = 0; for (int i = 1; i <= num; i++) { if (R < q[i].l || L > q[i].r) { for (int j = L; j <= R; j++) del(a[j]); L = q[i].l; R = q[i].r; for (int j = L; j <= R; j++) add(a[j]); } else { while (R < q[i].r) add(a[++R]); while (R > q[i].r) del(a[R--]); while (L < q[i].l) del(a[L++]); while (L > q[i].l) add(a[--L]); } ans[q[i].num] &= w; } for (int i = L; i <= R; i++) del(a[i]); for (int i = 1; i <= num / 3; i++) printf("%d\n", sum[i] - 3 * ans[i].count()); } int main() { n = read(); m = read(); for (int i = 1; i <= n; i++) { h[i].data = read(); b[h[i].data]++; h[i].num = i; } sort(h + 1, h + n + 1); int pre = 0, s = 0; for (int i = 1; i <= n; i++) { if (h[i].data == pre) a[h[i].num] = s; else { s += b[h[i].data]; pre = h[i].data; a[h[i].num] = s; } } solve(); solve(); solve(); return 0; }
-
-2
本代码需要开 O2。
#include<bits/stdc++.h> using namespace std; int n,m,bound,a[100010],b[100010],belong[100010],ans[25010],cnt[100010]; bool mark[25010]; void print(int x) { if(x<0)putchar('-'),x=-x; if(x>9)printf("%d",x/10); putchar(x%10+'0'); } int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } struct LINE { int l,r,id; bool operator<(const LINE &A)const { return belong[l]==belong[A.l]?r<A.r:l<A.l; } }line[76000]; bitset<100010>F[25010],f; void update(int pos,bool flag) { int x=a[pos]; if(flag) ++cnt[x],f[x+cnt[x]-2]=1; else f[x+cnt[x]-2]=0,--cnt[x]; } void solve(int t) { bound=0; memset(mark,0,sizeof(mark)); memset(ans,0,sizeof(ans)); for(int i=1;i<=t;i++) { for(int j=0;j<3;j++) { line[++bound].l=read(), line[bound].r=read(), line[bound].id=i; ans[i]+=line[bound].r-line[bound].l+1; } } sort(line+1,line+bound+1); f.reset(); memset(cnt,0,sizeof(cnt)); int L=1,R=0; for(int i=1;i<=bound;i++) { for(;R<line[i].r;update(++R,1)); for(;L>line[i].l;update(--L,1)); for(;R>line[i].r;update(R--,0)); for(;L<line[i].l;update(L++,0)); if(!mark[line[i].id]) F[line[i].id]=f,mark[line[i].id]=1; else F[line[i].id]&=f; } for(int i=1;i<=t;i++) { ans[i]-=F[i].count()*3; cout<<ans[i]<<'\n'; } } int main() { n=read(),m=read(); int S=sqrt(n); for(int i=1;i<=n;i++) { b[i]=read(),a[i]=b[i]; belong[i]=(i-1)/S+1; } sort(b+1,b+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b; while(m) { if(m<=25000) solve(m),m=0; else solve(25000),m-=25000; } return 0; }
- 1
信息
- ID
- 214
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 57
- 已通过
- 16
- 上传者