(mathcal{Description})
Link.
给定序列 ({(a,b)_n})，(q) 组形如 ((l,r,c,d)) 的询问，求
[Big|{iin[l,r]~ig|~a_ioplus cle min{b_i,d}}Big|
]
(n,qle10^5)，(a,b,c,d<2^{24})。
(mathcal{Solution})
CDQ 不熟练欸……
在 (i) 的限制条件中，最离谱的应该是 (lemin{b_i,d})，再联系部分分，可以想到分别计算两种情况。把原序列当做单点修改，询问离线为前缀查询，发现这就是一个偏序对的贡献问题，外层套一个 CDQ 分治处理。
接下来，我们需要应对动态插入和询问，分 ((a,b)) 一定用 (c) 查询和 (a) 一定用 ((c,d)) 查询两种情况写两棵不需要持久化的 Trie 树分别维护即可。
复杂度 (mathcal O((n+q)log(n+q)logmax{a,b,c,d}))。
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <algorithm>
#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )
#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )
inline int rint() {
int x = 0, f = 1, s = getchar();
for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
return x * f;
}
template<typename Tp>
inline void wint( Tp x ) {
if ( x < 0 ) putchar( '-' ), x = -x;
if ( 9 < x ) wint( x / 10 );
putchar( x % 10 ^ '0' );
}
const int MAXN = 1e5, MAXWID = 23;
int n, q, a[MAXN + 5], b[MAXN + 5], qall, ans[MAXN * 2 + 5];
int otmp[MAXN * 3 + 5], ord[MAXN * 3 + 5];
struct Event {
int r, c, d, id;
Event(): r( 0 ), c( 0 ), d( 0 ), id( 0 ) {}
Event( const int r_, const int c_, const int d_, const int id_ ):
r( r_ ), c( c_ ), d( d_ ), id( id_ ) {}
inline bool operator < ( const Event& t ) const {
return r != t.r ? r < t.r : id < t.id;
}
} evt[MAXN * 3 + 5];
struct DTrie { // maintain a[i] xor c <= d.
static const int MAXND = 2.3e6;
int node, root, siz[MAXND + 5], ch[MAXND + 5][2];
DTrie() { clear(); }
inline void clear() { node = root = 1, siz[1] = ch[1][0] = ch[1][1] = 0; }
inline int crtnd() {
int u = ++node;
siz[u] = ch[u][0] = ch[u][1] = 0;
return u;
}
inline void insert( int& u, const int x, const int d ) {
if ( !u ) u = crtnd();
++siz[u];
if ( ~d ) insert( ch[u][( x >> d ) & 1], x, d - 1 );
}
inline int query( const int u, const int c, const int lim, const int d ) {
if ( !u ) return 0;
if ( !~d ) return siz[u];
int p = c >> d & 1, q = lim >> d & 1, ret = 0;
if ( q ) return siz[ch[u][p]] + query( ch[u][!p], c, lim, d - 1 );
else return query( ch[u][p], c, lim, d - 1 );
}
} dtr;
struct BTrie { // maintain a[i] xor c <= b[i].
static const int MAXND = 2.3e6;
int node, root, tag[MAXND + 5], ch[MAXND + 5][2];
BTrie() { clear(); }
inline void clear() { node = root = 1, tag[1] = ch[1][0] = ch[1][1] = 0; }
inline int crtnd() {
int u = ++node;
tag[u] = ch[u][0] = ch[u][1] = 0;
return u;
}
inline void insert( int& u, const int a, const int b, const int d ) {
if ( !u ) u = crtnd();
if ( !~d ) return void( ++tag[u] );
int p = a >> d & 1, q = b >> d & 1;
if ( q ) {
if ( !ch[u][p] ) ch[u][p] = crtnd();
++tag[ch[u][p]];
insert( ch[u][p ^ 1], a, b, d - 1 );
} else {
insert( ch[u][p], a, b, d - 1 );
}
}
inline int query( const int u, const int c, const int d ) {
if ( !u ) return 0;
int ret = tag[u];
if ( !~d ) return ret;
return ret + query( ch[u][c >> d & 1], c, d - 1 );
}
} btr;
inline void solve( const int l, const int r ) {
if ( l >= r ) return ;
int mid = l + r >> 1, i, j, k;
solve( l, mid ), solve( mid + 1, r );
btr.clear(), i = l, j = mid + 1, k = l;
while ( i <= mid || j <= r ) {
if ( j > r || ( i <= mid && evt[ord[i]].d <= evt[ord[j]].d ) ) {
if ( !evt[ord[i]].id ) {
btr.insert( btr.root, evt[ord[i]].c, evt[ord[i]].d, MAXWID );
}
otmp[k++] = ord[i++];
} else {
if ( evt[ord[j]].id ) {
ans[evt[ord[j]].id] +=
btr.query( btr.root, evt[ord[j]].c, MAXWID );
}
otmp[k++] = ord[j++];
}
}
dtr.clear(), i = mid, j = r;
while ( i >= l || j > mid ) {
if ( j == mid || ( i >= l && evt[ord[i]].d > evt[ord[j]].d ) ) {
if ( !evt[ord[i]].id ) {
dtr.insert( dtr.root, evt[ord[i]].c, MAXWID );
}
--i;
} else {
if ( evt[ord[j]].id ) {
ans[evt[ord[j]].id] +=
dtr.query( dtr.root, evt[ord[j]].c, evt[ord[j]].d, MAXWID);
}
--j;
}
}
rep ( i, l, r ) ord[i] = otmp[i];
}
int main() {
n = rint(), q = rint();
rep ( i, 1, n ) {
int a = rint(), b = rint();
evt[++qall] = Event( i, a, b, 0 );
}
rep ( i, 1, q ) {
int l = rint(), r = rint(), c = rint(), d = rint();
evt[++qall] = Event( l - 1, c, d, ( i << 1 ) - 1 );
evt[++qall] = Event( r, c, d, i << 1 );
}
rep ( i, 1, qall ) ord[i] = i;
std::sort( evt + 1, evt + qall + 1 );
solve( 1, qall );
rep ( i, 1, q ) wint( ans[i << 1] - ans[( i << 1 ) - 1] ), putchar( '
' );
return 0;
}
(mathcal{Details})
好久没写这个板块了。
且不谈考场上能不能解出这道题，给这道题留的思考时间短得明显不合理。一来是策略问题——明明知道难度可能无需，却还骗自己说别人都把 T1 切了然后想了半天；二来，有些不习惯 (3.5h) 这种到长不短的比赛时间。
哎，今后尝试优化考试策略叭。