63.P5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III

给你一个长为 \(n\) 的序列 \(a\)，\(m\) 次询问，每次查询一个区间的众数的出现次数，强制在线。

题意简述

区间众数出现次数强制在线。

题解

三个 YLST 中比较清新的一个分块。

比较重点的地方在于询问散块的处理。

先离散化一下序列。

我们首先预处理出来一个 vector 数组 fur[i]，fur[i] 里面依次存的是所有 isa[i]（即这个序列，详见代码）的出现位置，再预处理一个 pos[i] 表示在当前第 \(i\) 位时 fur[i] 的大小也就是一共出现了多少个 isa[i]。由于 vector 的下标是从 \(0\) 开始的，所以所有的 pos[i] 都需要减个一。

然后询问处理整块的时候，我们先假设当前询问的区间是 [opl,opr]，然后把当前询问的答案 res 先置为 App[bel[opl] + 1][bel[opr] - 1]。

然后来考虑散块，在处理出的 vector 数组中判断即可。

设散块处理到数 isa[i]，那么如果存在 pos[i] + res <= fur[isa[i]].size() - 1 且 fur[isa[i]][pos[i] + res] <= opr，那么则说明这个数出现了至少 res + 1 次，将 res 加一即可。

由于 res 最多加不超过 \(\Theta(2\sqrt{n})\) 次，所以复杂度是对的。

#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 5e5 + 5, MAXM = 720 + 5;

char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar( ) ( p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1 ++ )

template
void read( _T &x ){
	x = 0; char c = getchar( ); _T f = 1;
	while( c < '0' || c > '9' ){ if( c == '-' )	f = -1; c = getchar( ); }
	while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar( ); }
	x *= f;
}

template
void write( _T x ){
	if( x < 0 ){ putchar( '-' ); x = -x; }
	if( x > 9 ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

template
void swapp( _T &one, _T &another ){ int temp = one; one = another; another = temp; }

template
_T MIN( _T one, _T another ){ return one > another ? another : one; }

template
_T MAX( _T one, _T another ){ return one > another ? one : another; }

int N, M;
int cube, each, kase, isa[MAXN], cnt[MAXN], pos[MAXN], vis[MAXN], bel[MAXN];
int lps[MAXM], rps[MAXM], app[MAXM], App[MAXM][MAXM];
vector disc, fur[MAXN];

int getID( int x ){ return lower_bound( disc.begin( ), disc.end( ), x ) - disc.begin( ) + 1; }

void build( ){
	for( int i = 1; i <= cube; ++ i ){
		kase ++;
		for( int j = lps[i]; j <= rps[i]; ++ j ){
			if( vis[isa[j]] != kase )	cnt[isa[j]] = 0;
			cnt[isa[j]] ++; app[i] = MAX( app[i], cnt[isa[j]] );
			vis[isa[j]] = kase;
		}
	}
	memset( cnt, 0, sizeof( cnt ) );
	for( int i = 1; i <= cube; ++ i ){
		kase ++;
		for( int j = i; j <= cube; ++ j ){
			App[i][j] = App[i][j - 1];
			for( int k = lps[j]; k <= rps[j]; ++ k ){
				if( vis[isa[k]] != kase )	cnt[isa[k]] = 0;
				cnt[isa[k]] ++; App[i][j] = MAX( App[i][j], cnt[isa[k]] );
				vis[isa[k]] = kase;
			}
		}
	}
	memset( cnt, 0, sizeof( cnt ) );
}

int query( int opl, int opr ){
	if( bel[opl] == bel[opr] ){
		int res = 0; kase ++;
		for( int i = opl; i <= opr; ++ i ){
			if( vis[isa[i]] != kase )	cnt[isa[i]] = 0;
			cnt[isa[i]] ++; res = MAX( res, cnt[isa[i]] );
			vis[isa[i]] = kase;
		}
		return res;
	}
	int res = 0;
//	res = App[bel[opl] + 1][bel[opr] - 1];
	for( int i = bel[opl] + 1; i < bel[opr]; ++ i )	res += app[i];
//	for( int i = bel[opl] + 1; i < bel[opr]; ++ i )	res += App[i][i];
	for( int i = opl; i <= rps[bel[opl]]; ++ i ){
		int lim = fur[isa[i]].size( ) - 1;
		while( pos[i] + res <= lim && fur[isa[i]][pos[i] + res] <= opr )	res ++;
	}
	for( int i = lps[bel[opr]]; i <= opr; ++ i ){
		while( pos[i] - res >= 0 && fur[isa[i]][pos[i] - res] >= opl )	res ++;
	}
	return res;
}

signed main( ){
	read( N ); read( M ); each = 720; cube = ( N - 1 ) / each + 1;
	for( int i = 1; i <= N; ++ i ){ read( isa[i] ); disc.push_back( isa[i] ); }
	sort( disc.begin( ), disc.end( ) );
	disc.erase( unique( disc.begin( ), disc.end( ) ), disc.end( ) );
	for( int i = 1; i <= N; ++ i ){
		isa[i] = getID( isa[i] );
		fur[isa[i]].push_back( i );
		pos[i] = fur[isa[i]].size( ) - 1;
	}
	for( int i = 1; i <= cube; ++ i ){
		lps[i] = rps[i - 1] + 1; rps[i] = rps[i - 1] + each;
		if( i == cube )	rps[i] = N;
		for( int j = lps[i]; j <= rps[i]; ++ j )	bel[j] = i;
	}
	build( );
	int Ans = 0, opl, opr;
	while( M -- > 0 ){
		read( opl ); read( opr ); opl ^= Ans; opr ^= Ans;
		Ans = 0; if( opl > opr )	swapp( opl, opr );
		write( Ans = query( opl, opr ) ); putchar( '\n' );
	}
	return 0;
}

64.「LibreOJ β Round #4」框架

没想到吧，我他娘的更新了

看到这道题

WGY说：bitset优化轻松过掉

LJS说：bitset优化裸题

ljs说：暴力打表能过！

那么这里是数据结构一百题，怎么能用这些方法呢？

所以我们来看看这道题吧：

有一个 \(n\times m\)的矩形框架，但其中有些边被删除了。\(\operatorname{qmqmqm}\) 想知道剩余部分中还有多少完整的正方形。

\(2\leq n,m\leq 10^3\)

先不看数据范围

考虑最朴素的暴力

三重循环分别枚举：左上角横坐标，左上角纵坐标，正方形边长

时间复杂度\(n^3\)

妥妥超时

那我们怎么优化呢

开一个数组记录一个点往左和往上最多能往上走几条边，由于是正方形，取这两个值中较小的一个就行了。

那么我们可以知道以每个点为右下角时正方形的边长最大值。

只需要再判断左上角是否能够走那么长了。

我们发现，以一个点为正方形的右下角时，可能的左上角位置在一条直线上，那么我们可以直接处理这一条直线。

每个点有往左上可以走到的最大距离，我们可以求出每个点往右下走的最大距离。如果两个点可以互相到达，那么它们就可以作为一个正方形的两个顶点。

我们可以用主席树解决上面的问题：版本 \(i\) 记录第 \(1\) 到 \(i\) 的点往前最多可以到达哪个点。

我们只在最远点上加个 \(1\)。因为之后查询会考虑到的。

再枚举每个点，查询从它后面到它往后最多能跳到的点中有多少点能够跳到它。

也就是这个区间的点中有多少个点能跳到的最远点小于等于它。

为什么有小于？因为如果能跳到更前面，那肯定能跳到这里。这就是之前只在最远点上加 \(1\) 的原因。（其实区间加单点查也是可以的）

对于前面记录最多能跳到哪里的数组，我们用二分来获取它。

总时间复杂度：

二分：\(n^2logn\)（每个点一次二分）

主席树:\(n^2logn\)（主席树对每个点操作一次）

总：\(n^2logn\)（因为二分和主席树是两个分开的部分）

跑不过 \(bitset\) 嘤嘤嘤...

代码：（注意细节）

#include
#include
using namespace std;
int n,m,lsum[1010][1010],hsum[1010][1010],dp[1010][1010],root[1010],ans,tot;
struct node
{
	int l,r,num;
}nodes[100010];
int search(int l,int r,int x,int y)
{
	while(l+1>1;
		if(lsum[x][y]-lsum[x-mid][y]==mid&&hsum[x][y]-hsum[x][y-mid]==mid)	l=mid;
		else	r=mid;
	}
	return l;
}
int exsearch(int l,int r,int x,int y)
{
	while(l+1>1;
		if(lsum[x+mid][y]-lsum[x][y]==mid&&hsum[x][y+mid]-hsum[x][y]==mid)	l=mid;
		else	r=mid;
	}
	return l;
}
void ins(int l,int r,int pre,int &now,int pos)
{
	now=++tot;
	nodes[now]=nodes[pre];
	++nodes[now].num;
	if(l^r)
	{
		int mid=(l+r)>>1;
		if(pos<=mid)	ins(l,mid,nodes[pre].l,nodes[now].l,pos);
		else	ins(mid+1,r,nodes[pre].r,nodes[now].r,pos);
	}
}
int find(int l,int r,int v1,int v2,int fr,int ba)
{
	if(l>ba||r=fr&&r<=ba)	return nodes[v2].num-nodes[v1].num;
	int mid=(l+r)>>1;
	return find(l,mid,nodes[v1].l,nodes[v2].l,fr,ba)+find(mid+1,r,nodes[v1].r,nodes[v2].r,fr,ba);
}
void solve(int x,int y)
{
	tot=0;
	int siz=min(n-x,m-y)+1;
	for(int i=x,j=y,k=1;i<=n&&j<=m;++i,++j,++k)	ins(1,siz,root[k-1],root[k],k-dp[i][j]);
	for(int i=x,j=y,k=1;i<=n&&j<=m;++i,++j,++k)	ans+=find(1,siz,root[k],root[k+exsearch(0,min(n-i,m-j)+1,i,j)],1,k);
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		for(int j=2;j<=m;++j)
		{
			scanf("%d",&hsum[i][j]);
			hsum[i][j]+=hsum[i][j-1];
		}
	}
	for(int i=2;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			scanf("%d",&lsum[i][j]);
			lsum[i][j]+=lsum[i-1][j];
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			dp[i][j]=search(0,min(i,j),i,j);
		}
	}
	for(int i=1;i<=m;++i)	solve(1,i);
	for(int i=2;i<=n;++i)	solve(i,1);
	printf("%d",ans);
	return 0;
}

65. P4689 [Ynoi2016]这是我自己的发明

我首先认为这是 SNOI2017 一个简单的询问 搬到树上。

我们传统地把此题分为两个 \(\texttt{pass}\)，一个询问，一个修改。

• \(\texttt{pass 1}\)：询问

我直接按 一个简单的询问 的方法讲。其实是把以前的题解 copy 过来了。

由于是出现次数，满足区间加减性，所以我们可以这样表达 \(\mathrm{get}(l,r,x)\)（省略 \(x\)）:

那么我们代进原式，化一波式子（\(\mathrm{get}(p)=\mathrm{get}(1,p,x)\)）：

则答案为:

考虑怎么更新，比如从 \(l\) 更新到 \(l+1\)，则：

其中 \(\mathrm{cont}(a_{l})\) 表示 \(a_{l}\) 的出现次数。

则我们就知道怎么更新了，由于我们维护和的是前缀信息，所以姿势和普通莫队有点不一样。

维护两个数组 cntl[x] 和 cntr[y] 表示答案式子

子树的话直接 DFS 序拍到序列上。

• \(\texttt{pass 2}\)：修改

现在我们面临着查询操作我们是用莫队整的，但这个修改貌似不单纯。其实也是从树剖模板缝合过来的。

分类讨论，设我们当前要换的根为 \(rt\)，现在来处理询问，设查询的节点为 \(u\)，\(\text{LCA}(u,v)\) 为节点 \(u\) 和节点 \(v\) 的最近公共祖先。

• • 如果 \(rt=u\)，则我们直接对整棵树进行查询。
• • 如果 \(\text{LCA}(u,rt)\neq u\)，此时修改不影响查询。
• • 如果 \(\text{LCA}(u,rt)=u\)，此时 \(rt\) 在 \(u\) 的子树里，那么需要查询的地方就很明确了，后面的步骤显然。

于是我们不需要实际的去处理这个修改，然后就可以直接莫队了。

（整体感觉是个 原题+假上树+树剖模板 的缝合题）

/* Clearink */

#include 
#include 

using namespace std;
typedef long long LL;

const int MAXN = 5e5 + 5, MAXM = 1e6 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

template void swapp ( _T& x, _T& y ) { _T w = x; x = y; y = w; }

struct GraphSet {
	int to, nx;
	GraphSet () : to ( 0 ), nx ( 0 ) {}
	GraphSet ( const int a, const int b ) : to ( a ), nx ( b ) {}
} asg[MAXN * 2];

struct Quest {
	int l, r, ID, x;
	Quest () : l ( 0 ), r ( 0 ), ID ( 0 ), x ( 0 ) {}
	Quest ( const int a, const int b, const int c, const int d ) : l ( a ), r ( b ), ID ( c ), x ( d ) {}
} asq[MAXM * 8], itls[MAXN];

LL cur = 0, ans[MAXM], buc1[MAXN], buc2[MAXN];
int rt, pos[MAXN], blo = 320, col[MAXN], freq;
int n, m, bgn[MAXN], cnt, sjc, segl[MAXN], segr[MAXN], kfa[MAXN][21], a[MAXN], dept[MAXN], pri[MAXN], len;

void addE ( const int u, const int v ) { asg[++ cnt] = GraphSet ( v, bgn[u] ), bgn[u] = cnt; }
bool existcmp ( const Quest& one, const Quest& ano ) { return pos[one.l] == pos[ano.l] ? one.r < ano.r : one.l < ano.l; }

void dfs ( const int u, const int lst ) {
	kfa[u][0] = lst, dept[u] = dept[lst] + 1;
	segl[u] = ++ sjc, col[sjc] = a[u];
	for ( int i = 1; i <= 20; ++ i )	kfa[u][i] = kfa[kfa[u][i - 1]][i - 1];
	for ( int i = bgn[u]; i; i = asg[i].nx ) {
		int v = asg[i].to;
		if ( v == lst )	continue;
		dfs ( v, u );
	}
	segr[u] = sjc;
}

int calcKAC ( int u, int k ) {
	for ( int i = 20; ~ i; -- i ) {
		if ( k >= ( 1 << i ) )	k -= ( 1 << i ), u = kfa[u][i];
	}
	return u;
}

int calcLCA ( int u, int v ) {
	if ( dept[u] < dept[v] )	swapp ( u, v );
	for ( int i = 20; ~ i; -- i ) {
		if ( dept[kfa[u][i]] >= dept[v] )	u = kfa[u][i];
	}
	if ( u == v )	return u;
	for ( int i = 20; ~ i; -- i ) {
		if ( kfa[u][i] != kfa[v][i] )	u = kfa[u][i], v = kfa[v][i];
	}
	return kfa[u][0];
}

void initial () {
	for ( int i = 1; i <= n; ++ i )	pos[i] = ( i - 1 ) / blo + 1;
	sort ( pri + 1, pri + 1 + n );
	len = unique ( pri + 1, pri + 1 + n ) - pri - 1;
	for ( int i = 1; i <= n; ++ i )	a[i] = lower_bound ( pri + 1, pri + 1 + len, a[i] ) - pri;
	dfs ( 1, 0 );
}

void splitASdrug ( const int u, int& ils ) {
	if ( u == rt )	itls[++ ils] = Quest ( 1, n, 0, 0 );
	else {
		int lca = calcLCA ( u, rt );
		if ( lca != u )	itls[++ ils] = Quest ( segl[u], segr[u], 0, 0 );
		else {
			int ar = calcKAC ( rt, dept[rt] - dept[u] - 1 );
			if ( 1 <= segl[ar] - 1 )	itls[++ ils] = Quest ( 1, segl[ar] - 1, 0, 0 );
			if ( segr[ar] + 1 <= n )	itls[++ ils] = Quest ( segr[ar] + 1, n, 0, 0 );
		}
	}
}

void transASsub ( const int l1, const int r1, const int l2, const int r2, const int ID ) {
	asq[++ m] = Quest ( r1, r2, ID, 1 ), asq[++ m] = Quest ( r1, l2 - 1, ID, -1 );
	asq[++ m] = Quest ( l1 - 1, r2, ID, -1 ), asq[++ m] = Quest ( l1 - 1, l2 - 1, ID, 1 );
}

void transASmany ( const int l, const int r ) {
	++ freq;
	int ils = 0; splitASdrug ( l, ils );
	int aim = ils; splitASdrug ( r, ils );
	for ( int i = 1; i <= aim; ++ i ) {
		for ( int j = aim + 1; j <= ils; ++ j )	transASsub ( itls[i].l, itls[i].r, itls[j].l, itls[j].r, freq );
	}
}

void add1 ( const int x ) { cur += buc2[col[x]], buc1[col[x]] ++; }
void add2 ( const int x ) { cur += buc1[col[x]], buc2[col[x]] ++; }
void sub1 ( const int x ) { cur -= buc2[col[x]], buc1[col[x]] --; }
void sub2 ( const int x ) { cur -= buc1[col[x]], buc2[col[x]] --; }
void captainMO () {
	int nowl = 0, nowr = 0;
	for ( int i = 1; i <= m; ++ i ) {
		for ( ; nowl < asq[i].l; add1 ( ++ nowl ) ) ;
		for ( ; nowr < asq[i].r; add2 ( ++ nowr ) ) ;
		for ( ; nowl > asq[i].l; sub1 ( nowl -- ) ) ;
		for ( ; nowr > asq[i].r; sub2 ( nowr -- ) ) ;
		ans[asq[i].ID] += cur * asq[i].x;
	}
}

int main () {
	n = rint (); int _waste_ = rint ();
	for ( int i = 1; i <= n; ++ i )	a[i] = pri[i] = rint ();
	for ( int i = 1; i < n; ++ i ) {
		int u = rint (), v = rint ();
		addE ( u, v ), addE ( v, u );
	}
	initial (), rt = 1;
	for ( int i = 1; i <= _waste_; ++ i ) {
		int c = rint (), x, y;
		if ( c == 1 )	rt = rint ();
		else	x = rint (), y = rint (), transASmany ( x, y );
	}
	sort ( asq + 1, asq + 1 + m, existcmp ), captainMO ();
	for ( int i = 1; i <= freq; ++ i )	wint ( ans[i] ), putchar ( '\n' );
	return 0;
}

66. CF1491H Yuezheng Ling and Dynamic Tree

所以 Chinese Round 出 DS 是传统了对吧。

Description

Link.

Given is a rooted tree with the \(\sf1\)-th node as the root.

The tree will be given in this way: it will tell you that the parent of the \(\sf i\)-th node is \(a_{i}\).

Supporting the following operations:

• 1 l r x: let \(\sf \forall i\in[l,r],a_{i}=max\{a_{i}-x,1\}\).
• 2 u v: find the LCA (Lowest Common Ancestor) of \(\sf u\) and \(\sf v\).

Solution

经典永流传。

考虑到修改操作是对结点进行的操作，然后这个东西不太能直接 LCT 或树剖，考虑照序列来分块，那么我们来对结点编号分块。

1. 修改；

\(\quad\)维护一个属性 \(\sf top_{u}\) 表示在原树上结点 \(\sf u\) 的祖先中不和 \(\sf u\) 在同一个块里面的编号最大的一个结点的编号，如果不存在的话就令 \(\sf top_{u}=1\)。这样的话你从结点 \(\sf u\) 跳到 root 的复杂度为 \(\sf O(\sqrt{n})\)。接下来考虑怎么维护这个东西。

\(\quad\)散块我们直接暴力扫着改；对于整块，可以发现如果一个块的被修改次数超过了块的大小，那么就一定会有 \(\sf top_{u}=fa_{u}\)。

2. 询问。

\(\quad\)分三个类讨论，这个比较好做（差不多和树剖找 LCA 一个样子）。

#include
using namespace std;
int n,m,top[100010],deln[320],tag[320],belong[100010],bl[320],br[320],fa[100010],bs;
#define gtlf(x) ((x-1)*bs+1)
#define gtrg(x) (min(x*bs,n))
void updtop(int x)
{
	if(belong[x]^belong[fa[x]])	top[x]=fa[x];
	else	top[x]=top[fa[x]];
}
void turndown(int x)
{
	if(tag[x])
	{
		for(int i=gtlf(x);i<=gtrg(x);++i)	fa[i]=max(fa[i]-tag[x],1);
		tag[x]=0;
	}
}
int main()
{
	scanf("%d %d",&n,&m),bs=sqrt(double(n))+1,fa[1]=belong[1]=1;
	for(int i=2;i<=n;++i)	scanf("%d",&fa[i]);
	for(int i=2;i<=n;++i)	belong[i]=(i-1)/bs+1,updtop(i);
	while(m--)
	{
		int opt; scanf("%d",&opt);
		if(opt==1)
		{
			int opl,opr,opx;
			scanf("%d %d %d",&opl,&opr,&opx);
			turndown(belong[opl]);
			if(belong[opl]==belong[opr])
			{
				turndown(belong[opl]);
				for(int i=opl;i<=opr;++i)	fa[i]=max(fa[i]-opx,1),updtop(i);
				for(int i=opr+1;i<=gtrg(belong[opl]);++i)	updtop(i);
			}
			else
			{
				turndown(belong[opl]);
				for(int i=opl;i<=gtrg(belong[opl]);++i)	fa[i]=max(fa[i]-opx,1),updtop(i);
				for(int i=gtlf(belong[opl]);i=bs)	tag[i]+=opx;
					else
					{
						++deln[i];
						for(int j=gtlf(i);j<=gtrg(i);++j)	fa[j]=max(fa[j]-opx,1),updtop(j);
					}
				}
			}
		}
		else
		{
			int opx,opy; scanf("%d %d",&opx,&opy);
			while(opx^opy)
			{
				int fopx,fopy;
				if(deln[belong[opx]]>=bs)	turndown(belong[opx]),fopx=fa[opx];
				else	fopx=top[opx];
				if(deln[belong[opy]]>=bs)	turndown(belong[opy]),fopy=fa[opy];
				else	fopy=top[opy];
				if(belong[opx]^belong[opy])
				{
					if(belong[opx]>belong[opy])	opx=fopx;
					else	opy=fopy;
				}
				else if(fopx^fopy)	opx=fopx,opy=fopy;
				else
				{
					if(opx>opy)	turndown(belong[opx]),opx=fa[opx];
					else	turndown(belong[opy]),opy=fa[opy];
				}
			}
			printf("%d\n",opx);
		}
	}
	return 0;
}

67. 「NOI2020」时代的眼泪

小 L 喜欢与智者交流讨论，而智者也经常为小 L 出些思考题。

这天智者又为小 L 构思了一个问题。智者首先将时空抽象为了一个二维平面，进而将一个事件抽象为该平面上的一个点，将一个时代抽象为该平面上的一个矩形。

为了方便，下面记 \((a, b) \leq (c, d)\) 表示平面上两个点 \((a, b),(c, d)\) 满足 \(a \leq c, b \leq d\)。

更具体地，智者给定了 \(n\) 个事件，他们用平面上 \(n\) 个不同的点 \(\{(x_i, y_i)\}^n_{i=1}\) 来表示；智者还给定了 \(m\) 个时代，每个时代用平面上一个矩形 \((r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2})\) 来表示，其中 \((r_{i,1}, c_{i,1})\) 是矩形的左下角，\((r_{i,2}, c_{i,2})\) 是矩形的右上角，保证 \((r_{i,1}, c_{i,1}) \leq (r_{i,2}, c_{i,2})\)。我们称时代 \(i\) 包含了事件 \(j\) 当且仅当 \((r_{i,1}, c_{i,1}) \leq (x_j, y_j ) \leq (r_{i,2}, c_{i,2})\)。

智者认为若两个事件 \(i, j\) 满足 \((x_i, y_i) \leq (x_j, y_j)\)，则这两个事件形成了一次遗憾。而对一个时代内包含的所有事件，它们所形成的遗憾被称为这个时代的眼泪，而形成的遗憾次数则称为该时代的眼泪的大小。现在智者想要小 L 计算每个时代的眼泪的大小。

小 L 明白，如果他回答不了这个问题，他也将成为时代的眼泪，请你帮帮他。

膜拜 dX。

基本是把 dX 的题解贺了过来所以没啥参考的价值。

不过有很多细节的处理不一样，大概能算个 \(\frac{1}{50}\) 成新？

对序列分块，把贡献分成 整块 - 散块 / 整块 - 整块/ 散块 - 整块 / 散块 - 散块 以及 散块内部 / 整块内部 共六种贡献。

记 \(\textit{ans}_{0}(l,r,x,y)\) 为询问 \(l,r,x,y\) 的答案。

同时预处理出 \(\textit{lb}(i,j),\textit{ub}(i,j)\) 分别表示在块 \(i\) 中数 \(j\) 的 std::lower_bound / std::upper_bound 值，下文如果写成单元函数的形式那么就是省去了第一维。

以及预先做一个块内排序，记为 \(\textit{ord}(i,j)\)，表示块 \(i\) 中排序后的第 \(j\) 个元素。

注意本文在每个 subtask 定义的东西在其他 subtask 依然适用。

• 散块 - 散块；

两边的都是 \(\sqrt{n}\) 级别，拉出来分别排序后归并计算顺序对即可。

• 散块内部

考虑如何对 \(\textit{ans}_{0}(l,r,x,y)\) 进行容斥。

主要矛盾集中在：会出现 \((a\in[1,x),b\in[x,y])\) 这样的贡献。令 \(\textit{cnt}_{0}(i,j)\) 表示 \([\textit{lp},i]\) 中 \(\textit{rank}_{1}\) 小于 \(j\) 的数的数量，其中 \(\textit{lp}\) 是当前块的左端点，下同，如果出现 \(\textit{rp}\) 同理，\(\textit{rank}_{1}\) 的定义见下文。

则容斥可以写为 \(\textit{ans}_{0}(l,r,x,y)=\textit{ans}_{0}(l,r,1,y)-\textit{ans}_{0}(l,r,1,x-1)-\sum_{i=l}^{r}[a_{i}\in[x,y]]\cdot\textit{cnt}_{0}(i,\textit{lb}(x)-1)\)。

又有 \(\textit{ans}_{0}(l,r,1,x)=\sum_{i=l}^{r}[a_{i}\leqslant x]\cdot\textit{cnt}_{0}(i,\textit{rank}_{1}(i))\)，我们就可以做到单次 \(\mathcal{O}(\sqrt{n})\)，注意的 \(l,r\) 触及散块边界者不同时，对 \(\textit{cnt}_{0}\) 的容斥也有区别。

• 整块 - 整块

令 \(\textit{cnt}_{1}(i,j)\) 为块 \([1,i]\) 中 \(\leqslant j\) 的元素个数，\(\textit{ans}_{1}(L,R,x,y)\) 为块 \([L,R]\) 的答案，以及 \(\textit{rank}_{0}(i,j)\) 是块 \(i\) 中排名 \(j\) 的元素在原数组中的下标。

我们掏出传统容斥：\(\textit{ans}_{1}(L,R,x,y)=\textit{ans}_{1}(L,R,1,y)-\textit{ans}_{1}(L,R,1,x-1)-\sum_{i=L}^{R}P_{i}Q_{i}\)，\(P_{i}\) 是块 \([L,i)\) 中 \( 的元素个数，\(Q_{i}\) 是块 \(i\) 种 \(\in[x,y]\) 的元素个数。

考虑算 \(\textit{ans}_{1}(L,R,1,x)\)。

定义 \(\textit{rank}_{1}(i,j)\) 为块 \(i\) 中第 \(j\) 个元素的排名（从小到大，下同），\(\textit{rank}_{2}(i,j)\) 为块 \(i\) 中满足 \( 的最大元素的排名，\(\textit{pre}_{b}(i,j)\) 为块 \([i,j]\) 中所有 \(<\textit{rank}_{1}(i,j)\) 的元素数量。

易知 \(\textit{pre}_{b}(i,j)=\textit{cnt}_{1}(i,\textit{rank}_{1}(i,j)-1)\)，再定义 \(\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{0}(i,L,r)}\) 为块 \([1,L]\) 与块 \(i\) 前 \(r\) 小的元素组成的顺序对数量，同样易知 \(\textit{cp}_{0}(i,L,r)=\sum_{k\in T}[\textit{rank}_{1}(i,k)\leqslant r]\cdot\textit{pre}_{b}(L,\textit{rank}_{1}(i,k))\)，其中 \(T\) 是块 \(i\) 的元素集。但这样搞状态数 \(\mathcal{O}(n\sqrt{n})\) 转移还要 \(\mathcal{\sqrt{n}}\) 而且不好前缀和。

不过可以发现使用 \(\textit{ord}\) 数组 \(\textit{cp}_{0}\) 就可以递推了：\(\textit{cp}_{0}(i,L,r)=\sum_{k=lp}^{r+lp-1}\textit{pre}_{b}(L,k)=\textit{cp}_{0}(i,L,r-1)+\textit{pre}_{b}(L,r+lp-1)\)。

然后 \(\textit{ans}_{1}(L,R,1,x)=\sum_{i=L+1}^{R}\textit{cp}_{0}(i,i-1,\textit{rank}_{2}(i,x))-\textit{cp}_{0}(i,L-1,\textit{rank}_{2}(i,x))\)。

预处理 \(\textit{cp}_{0}\) 是 \(\mathcal{O}(n\sqrt{n})\)，单次回答 \(\mathcal{O}(\sqrt{n})\)。

• 散块 - 整块

枚举散块里面的元素，利用 \(\textit{cnt}_{1}(i,j)\) 计算答案。

具体是令散块元素集为 \(T\)，整块编号为 \(L,R\)， \(\sum_{i\in T}\textit{cnt}_{1}(R,i)-\textit{cnt}_{1}(L-1,i)\)。

• 整块 - 散块

和上面有什么区别吗？

• 整块内部

预处理数组 \(\overset{\sqrt{n},\sqrt{n},\sqrt{n}}{\textit{cp}_{1}(i,x,y)}\) 表示取 \(\textit{ord}(i,x\dots y)\) 组成的序列的顺序对数量。

用 \(\textit{rank}_{0}\) 来预处理：\(\textit{cp}_{1}(i,x,y)=\textit{cp}_{1}(i,x,y-1)+\textit{cnt}_{0}(\textit{rank}_{0}(i,y),y-1)-\textit{cnt}_{0}(\textit{rank}_{0}(i,y),x-1)\)。

综上，这个问题得以一个 \(\mathcal{O}(n\sqrt{n})\) 的在线算法解决。

//almost copied from dead_X sry
//kouhu has no qiantu
#include
typedef long long ll;
using namespace std;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
	int x=0;char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9') x=x*10+(c&15),c=getchar();
	return x;
}
const int N=101111,A=400,BS=A+10;
ll cp0[BS][BS][BS];
int a[N],rk0[BS][BS],cnt0[N][BS],cp1[BS][BS][BS],lb[BS][N],rk1[N],cnt1[BS][N],L[BS],R[BS];
bool cmp(int x,int y) { return a[x]=a[rk0[i][k]])&&(++k),lb[i][j]=k;
	}
	for(int i=0;i<=B;++i)
		for(int j=1;j<=101000;++j)cnt1[i][j]+=cnt1[i][j-1];
	for(int i=1;i=l&&x<=a[rk0[bl][i]]&&a[rk0[bl][i]]<=y)L[++lt]=rk0[bl][i];
				if(rk0[br][i]<=r&&x<=a[rk0[br][i]]&&a[rk0[br][i]]<=y)R[++rt]=rk0[br][i];
			}
			for(int i=1,t=1;i<=rt;++i){
				while(t<=lt&&a[L[t]]