3 条题解

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

    第一道 Ynoi /se

    做法

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

    考虑 bitset 乱搞。

    发现答案为 A+B+C3×ABC|A|+|B|+|C|-3\times |A\cap B\cap C|

    其中 A+B+C|A|+|B|+|C| 很容易知道,考虑如何维护 ABC|A\cap B\cap C|

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

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

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

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

    假设有一个区间,要加入一个数 xx,设其在区间中出现的次数为 cntxcnt_x,则可以把 bitset 的第 xcntxx-cnt_x 位改为 11。显然这个 xcntxx-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

        信息

        ID
        214
        时间
        3000ms
        内存
        512MiB
        难度
        6
        标签
        (无)
        递交数
        57
        已通过
        16
        上传者