\(\mathcal{Description}\)

给定序列 \(\{a_n\}\)，处理 \(m\) 次操作：

给定 \(l,r,x\)，把 \([l,r]\) 内所有 \(>x\) 的数减去 \(x\)；
给定 \(l,r,x\)，查询 \([l,r]\) 内 \(x\) 的出现次数。

\(n\le10^6\)，\(m\le5\times10^5\)，\(0\le a_i,x\le10^5\)。

\(\mathcal{Solution}\)

巧妙的分块题。

分块，设块长为 \(B\)，对于每一块，利用值域 \(V\) 不大，直接使用桶的方式维护信息。把桶看做一条线段 \([v_l,v_r]\)，每次修改相当于把线段的后端截下一段平移到前端，可用启发式合并 + 并查集确保复杂度。最终复杂度为 \(\mathcal O(qB+\frac{nV}{B}+\frac{qn}{B})\)，大概取 \(B=1.5\times10^3\) 就好。注意卡空间，对每个块离线处理。

\(\mathcal{Code}\)

/*~Rainybunny~*/

#include <bits/stdc++.h>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

inline char fgc() {

	static char buf[1 << 17], *p = buf, *q = buf;

	return p == q && ( q = buf + fread( p = buf, 1, 1 << 17, stdin ), p == q )

	  ? EOF : *p++;

}

inline int rint() {

	int x = 0, s = fgc();

	for ( ; s < '0' || '9' < s; s = fgc() );

	for ( ; '0' <= s && s <= '9'; s = fgc() ) x = x * 10 + ( s ^ '0' );

	return x;

}

inline void wint( const int x ) {

	if ( 9 < x ) wint( x / 10 );

	putchar( x % 10 ^ '0' );

}

inline int imin( const int u, const int v ) { return u < v ? u : v; }

inline int imax( const int u, const int v ) { return u < v ? v : u; }

const int MAXN = 1e6, MAXM = 6e5, MAXV = 1e5, MAXS = 1500;

int n, m, a[MAXN + 5], ans[MAXM + 5];

struct Event { int op, l, r, x; } evt[MAXM + 5];

int fa[MAXN + 5], siz[MAXV + 5], rt[MAXV + 5], ref[MAXN + 5];

inline int find( const int x ) {

	return x == fa[x] ? x : fa[x] = find( fa[x] );

}

inline void unite( int x, int y ) {

	assert( rt[x] );

	if ( rt[y] ) fa[rt[x]] = rt[y];

	else ref[rt[y] = rt[x]] = y;

	siz[y] += siz[x], siz[x] = rt[x] = 0;

}

inline void solve( const int bl, const int br ) {

	int vl = 0, vr = 0;

	rep ( i, bl, br ) vr = a[i] < vr ? vr : a[i];

	memset( rt, 0, sizeof rt ), memset( siz, 0, sizeof siz );

	rep ( i, bl, br ) {

		if ( rt[a[i]] ) fa[i] = rt[a[i]];

		else rt[a[i]] = fa[i] = i, ref[i] = a[i];

		++siz[a[i]];

	}

	rep ( i, 1, m ) {

		int x = evt[i].x, l = evt[i].l, r = evt[i].r;

		if ( r < bl || l > br ) continue;

		if ( evt[i].op == 1 ) { // modify.

			if ( vr - vl <= x ) continue;

			if ( l <= bl && br <= r ) { // whole block update.

				if ( x << 1 > vr - vl ) { // right to left.

					per ( j, vr, vl + x + 1 ) if ( rt[j] ) unite( j, j - x );

					vr = vl + x;

				} else { // left to right.

					rep ( j, vl + 1, vl + x ) if ( rt[j] ) unite( j, j + x );

					vl += x;

				}

			} else { // partly update. curA = find(orgA)-vl.

				rep ( j, bl, br ) {

					a[j] = ref[find( j )];

					siz[a[j]] = rt[a[j]] = 0;

					a[j] -= vl;

				}

				vl = vr = 0;

				rep ( j, bl, br ) {

					l <= j && j <= r && a[j] > x && ( a[j] -= x );

					vr = vr < a[j] ? a[j] : vr;

					if ( rt[a[j]] ) fa[j] = rt[a[j]];

					else rt[a[j]] = fa[j] = j, ref[j] = a[j];

					++siz[a[j]];

				}

			}

		} else if ( vl + x <= vr ) { // meaningful query.

			if ( l <= bl && br <= r ) { // whole block query.

				ans[i] += siz[x + vl];

			} else { // partly query.

				rep ( j, imax( l, bl ), imin( r, br ) ) {

					ans[i] += ref[find( j )] - vl == x;

				}

			}

		}

	}

}

int main() {

    n = rint(), m = rint();

	rep ( i, 1, n ) a[i] = rint();

	rep ( i, 1, m ) {

		evt[i].op = rint();

		evt[i].l = rint(), evt[i].r = rint(), evt[i].x = rint();

	}

	for ( int l = 1, r; l <= n; l = r + 1 ) {

		r = l + MAXS - 1; if ( r > n ) r = n;

		solve( l, r );

	}

	rep ( i, 1, m ) if ( evt[i].op == 2 ) {

		wint( ans[i] ), putchar( '\n' );

	}

	return 0;

}

巴特西

Solution -「Ynoi 2018」「洛谷 P4117」五彩斑斓的世界

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章