3 条题解

  • 3
    @ 2021-10-22 10:34:12

    第一道 Ynoi /se

    做法

    这道题看起来就像不能用数据结构维护的样子。

    考虑 bitset 乱搞。

    发现答案为 ∣A∣+∣B∣+∣C∣−3×∣A∩B∩C∣|A|+|B|+|C|-3\times |A\cap B\cap C|。

    其中 ∣A∣+∣B∣+∣C∣|A|+|B|+|C| 很容易知道，考虑如何维护 ∣A∩B∩C∣|A\cap B\cap C|。

    首先要对数字进行离散化。

    但……普通的离散化后的值似乎无法维护。

    改一下离散化，令 xx 离散化后的值为 ∑i=1n[ai≤x]\sum_{i=1}^n [a_i\le x]。（其中 [表达式][表达式] 为当表达式成立时返回值是 11，不成立则为 00）。

    那么，设离散化后有两个数 x,yx,y，满足 x<yx<y，则 y−xy-x 为 >x>x 且 ≤y\le y 的数的个数。

    假设有一个区间，要加入一个数 xx，设其在区间中出现的次数为 cntxcnt_x，则可以把 bitset 的第 x−cntxx-cnt_x 位改为 11。显然这个 x−cntxx-cnt_x 不会与其它数重合。

    再看题目，不需要修改，这就不是莫队么！

    所以最终我们的解法就是 bitset+莫队 了。

    不过注意，我们开不下 105×10510^5 \times 10^5。

    其实只要分三次计算就好啦 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
      @ 2023-4-7 16:50:00 
      #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
        @ 2021-10-11 13:33:48

        本代码需要开 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

        [Ynoi2016] 掉进兔子洞

        信息

        ID
        214
        时间
        3000ms
        内存
        512MiB
        难度
        6
        标签
        (无)
        递交数
        57
        已通过
        16
        上传者
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        2. © 2021-2024 Hydro.ac
        4. Worker 0 in 304ms
        5. Hydro v4.18.0 Professional