礼物

题目大意：

数据范围：

题解：

这题有意思啊（$md$卡常

直接做怎么做？

随便上个什么东西，维护一下矩阵乘和插入，比如说常数还算小的$KD-Tree$（反正我是没见人过过

我们漏掉了一个条件，就是所有二元组都是随机的。

这个条件很好，它几乎就保证了，任选一个区间的话，优秀二元组只有$log$个。

这是为什么呢？

其实区间内，优秀二元组的个数，就相当于把区间按照$x$排序后，$y$值是前缀最大值的期望个数。

因为二元组是随机的，所以$x$排序后，$y$仍然是随机的。

就是给定一个随机数列，求前缀最大值的期望个数。

这是调和级数的。

所以，我们就开一棵线段树，线段树上每个节点维护一个数组，存这个节点管辖区间内的优秀二元组。

合并用归并，复杂度是$O(log)$的。

所以每次查询的复杂度是$O(log^2n)$的。

总复杂度是$O(nlog^2n)$的，有点小卡常，加了输出优化才过（读入优化是必备。

代码：

#include <bits/stdc++.h>

#define ls p << 1

#define rs p << 1 | 1

#define N 200010 

using namespace std;

const int mod = 1000000007 ;

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0;

	char c = nc();

	while (c < 48) {

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x;

}

char pbuf[100000],*pp=pbuf;

void push(const char c) {

    if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;

    *pp++=c;

}

void write(int x) {

    static int sta[35];

    int top=0;

    do{sta[top++]=x%10,x/=10;}while(x);

    while(top) push(sta[--top]+'0');

    push('\n');

}

struct Node {

	int x, y;

	friend bool operator < (const Node &a, const Node &b) {

		return a.x == b.x ? a.y < b.y : a.x < b.x;

	}

}num[N];

Node q[60];

struct Mode {

	Node v[30];

	int len;

	int sum;

	Mode() { len = 0, sum = 1; }

}a[N << 2];

inline Mode operator + (const Mode &a, const Mode &b) {

	Mode re;

	int cnt = 0;

	int j = 1;

	for (int i = 1; i <= a.len; i ++ ) {

		while ((j <= b.len) && (a.v[i] < b.v[j])) {

			q[ ++ cnt] = b.v[j];

			j ++ ;

		}

		q[ ++ cnt] = a.v[i];

	}

	while (j <= b.len) {

		q[ ++ cnt] = b.v[j];

		j ++ ;

	}

    // int i = 1, j = 1;

    // while (i <= a.len && j <= b.len) {

    //     if (a.v[i] < b.v[j]) {

    //         q[ ++ cnt] = a.v[i];

    //         i ++ ;

    //     }

    //     else {

    //         q[ ++ cnt] = b.v[j];

    //         j ++ ;

    //     }

    // }

    // while (i <= a.len) {

    //     q[ ++ cnt] = a.v[i];

    //     i ++ ;

    // }

    // while (j <= b.len) {

    //     q[ ++ cnt] = b.v[j];

    //     j ++ ;

    // }

    // for (int i = 1; i <= a.len; i ++ ) {

    //     q[ ++ cnt] = a.v[i];

    // }

    // for (int i = 1; i <= b.len; i ++ ) {

    //     q[ ++ cnt] = b.v[i];

    // }

    // sort(q + 1, q + cnt + 1);

	int mx = 0;

    for (int i = 1; i <= cnt; i ++ ) {

		if (q[i].y > mx) {

			re.v[ ++ re.len] = q[i];

			re.sum = (ll)re.sum * (q[i].x ^ q[i].y % mod) % mod;

			mx = q[i].y;

		}

	}

    // reverse(re.v + 1, re.v + re.len + 1);

	return re;

}

void build(int l, int r, int p) {

	if (l == r) {

		a[p].v[ ++ a[p].len] = num[l];

		a[p].sum = (num[l].x ^ num[l].y) % mod;

		return;

	}

	int mid = (l + r) >> 1;

	build(l, mid, ls);

	build(mid + 1, r, rs);

	a[p] = a[ls] + a[rs];

}

Mode query(int x, int y, int l, int r, int p) {

	if (x <= l && r <= y) {

		return a[p];

	}

	int mid = (l + r) >> 1;

    if (mid < x)

        return query(x, y, mid + 1, r, rs);

    else if(y <= mid)

        return query(x, y, l, mid, ls);

    else

        return query(x, y, l, mid, ls) + query(x, y, mid + 1, r, rs);

}

int main() {

	int n = rd();

	for (int i = 1; i <= n; i ++ ) {

		num[i].x = rd();

		num[i].y = rd();

	}

	build(1, n, 1);

	int q = rd();

	while(q -- ) {

		int x = rd(), y = rd();

		Mode now = query(x, y, 1, n, 1);

		write(now.sum);

	}

    fwrite(pbuf,1,pp-pbuf,stdout);

	return 0;

}

小结：这种期望的题还是要自己证才行，不然结论根本记不过来。

巴特西

[计蒜客T2238]礼物_线段树_归并排序_概率期望

礼物

最新文章

热门文章