夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

某金牌训练营Day12

2021-02-25 18 min read

A

首先S没用,S的大小和三元组不同的数数量相同

然后我们考虑怎么统计(x,y,z)=(maxax,maxay,maxaz)(x,y,z)=(max a_x,max a_y,max a_z)的三元组数量

如果∣S∣=1|S|=1可以直接统计,答案为n

∣S∣=2|S|=2,此时我们一个满足最大两维,然后另外一个点两维比他小第三维比他大

容斥掉,改为统计三个都不满足,然后减去即可

∣S∣=3|S|=3

有多少大小为3的下标子集,满足a,b,c最大下标不同

还是容斥,首先减去最大值都出现在一个的方案数,这个是直接数点计算

然后最大值出现在两个的方案数,其中有一个拿到了两个最大值,这个可以树状数组容斥求,不考虑其中一个拿到三个最大值,然后减去其中一个拿到三个最大值的方案数,不难发现我们统计三遍会算重三遍第一类的方案数,减去即可

然后总方案数减一下即可

数点用树套树实现的话你就只能一遍查询就这样容斥两边了

//艹10次询问被我压到1次真不错
//艹树套树
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 4e5 + 7;
const int MAXT = 3e7 + 7;
ll ans;
int n, rt;
struct rec {
	int a, b, c;
} a[MAXN];

bool cmpa(rec x, rec y) {
	return x.a < y.a;
}

bool cmpb(rec x, rec y) {
	return x.b < y.b;
}

bool cmpc(rec x, rec y) {
	return x.c < y.c;
}

namespace seg2 {
#define mid ((l+r)>>1)
	int ls[MAXT], rs[MAXT], T, tr[MAXT];
	inline void mdf(int &k, int l, int r, int P) {
		if(!k)k = ++T;
		tr[k]++;
		// printf("mdf2! %d %d %d\n", k, P, tr[k]);
		if(l == r)return ;
		if(P <= mid)mdf(ls[k], l, mid, P);
		else mdf(rs[k], mid + 1, r, P);
	}
	inline int qry(int k, int l, int r, int L, int R) {
		// printf("%d %d %d %d %d %d\n", k, l, r, L, R, tr[k]);
		if(L <= l && r <= R)return tr[k];
		if(R <= mid)return qry(ls[k], l, mid, L, R);
		else if(L > mid)return qry(rs[k], mid + 1, r, L, R);
		else return qry(ls[k], l, mid, L, R) + qry(rs[k], mid + 1, r, L, R);
	}
	inline void clear() {
		assert(T < MAXT);
		memset(ls, 0, sizeof(ls));
		memset(rs, 0, sizeof(rs));
		memset(tr, 0, sizeof(tr));
		T = 0;
		// puts("!!!qwq");
	}
}

namespace seg {
	int ls[MAXN], rs[MAXN], rt2[MAXN], T; //第二棵树上的根??
	inline void mdf(int &k, int l, int r, int P, int x) {
		if(!k)k = ++T;
		seg2::mdf(rt2[k], 1, n, x);//单点插入
		if(l == r)return ;
		if(P <= mid)mdf(ls[k], l, mid, P, x);
		else mdf(rs[k], mid + 1, r, P, x);
	}
	inline int qry(int k, int l, int r, int L1, int R1, int L2, int R2) {
		if(!k)return 0;
		// printf("%d %d %d %d %d %d %d\n", k, l, r, L1, R1, L2, R2);
		if(L1 <= l && r <= R1) {
			// puts("In->");
			return seg2::qry(rt2[k], 1, n, L2, R2);
		}
		if(R1 <= mid)return qry(ls[k], l, mid, L1, R1, L2, R2);
		else if(L1 > mid)return qry(rs[k], mid + 1, r, L1, R1, L2, R2);
		else return qry(ls[k], l, mid, L1, R1, L2, R2) + qry(rs[k], mid + 1, r, L1, R1, L2, R2);
	}
	inline void clear() {
		rt = 0;//坑
		seg2::clear();
		memset(rt2, 0, sizeof(rt2));
		memset(ls, 0, sizeof(ls));
		memset(rs, 0, sizeof(rs));
		T = 0;
		// puts("!!!!QAQ");
	}
#undef mid
}

namespace BIT {
#define lowbit(x) (x&(-x))
	int tr[MAXN];
	inline void add(int x, int w) {
		for(; x <= n; x += lowbit(x))tr[x] += w;
	}
	inline void clear() {
		memset(tr, 0, sizeof(tr));
	}
	inline ll qry(int x) {
		ll ret = 0;
		for(; x; x -= lowbit(x))ret += tr[x];
		return ret;
	}
}

inline void solve() {
	ans = n;
	ll tmp1 = 0;
	if(n >= 2) {//数有二维小于等于他的数
		// sort(a + 1, a + n + 1, cmpa);
		// for(int i = 1; i <= n; ++i) {
		// 	ans += seg::qry(rt, 1, n, 1, a[i].b, a[i].c, n); //a,b两维都小于他
		// 	seg::mdf(rt, 1, n, a[i].b, a[i].c);
		// 	// printf("ab %d %d %d\n", i, a[i].a, ans);
		// }
		// seg::clear();
		// for(int i = 1; i <= n; ++i) {
		// 	ans += seg::qry(rt, 1, n, 1, a[i].c, a[i].b, n); //a,c两维都小于他
		// 	seg::mdf(rt, 1, n, a[i].c, a[i].b);
		// 	// printf("ac %d %d %d\n", i, a[i].a, ans);
		// }
		// seg::clear();
		// sort(a + 1, a + n + 1, cmpb);
		// for(int i = 1; i <= n; ++i) {
		// 	ans += seg::qry(rt, 1, n, 1, a[i].c, a[i].a, n);//b,c两维都小于他
		// 	seg::mdf(rt, 1, n, a[i].c, a[i].a);
		// 	// printf("bc %d %d %d\n", i, a[i].b, ans);
		// }
		// seg::clear();
		ans += 1ll * n * (n - 1) / 2;
		sort(a + 1, a + n + 1, cmpa);//三个都是最大的
		for(int i = 1; i <= n; ++i) {
			ll qwq = seg::qry(rt, 1, n, 1, a[i].b, 1, a[i].c);
			tmp1 += qwq * (qwq - 1) / 2;
			ans -= qwq;//三个都小于,等价于取反之后一个
			seg::mdf(rt, 1, n, a[i].b, a[i].c);//b,c都小于他
		}
	}
	if(n >= 3) {//容斥
		ll tmp = 0;
		for(int i = 1; i <= n; ++i) {
			ll qwq = BIT::qry(a[i].b); //a,b
			tmp += qwq * (qwq - 1) / 2;
			BIT::add(a[i].b, 1);
		}
		BIT::clear();
		for(int i = 1; i <= n; ++i) {
			ll qwq = BIT::qry(a[i].c);//a,c
			tmp += qwq * (qwq - 1) / 2;
			BIT::add(a[i].c, 1);
		}
		BIT::clear();
		sort(a + 1, a + n + 1, cmpb);
		for(int i = 1; i <= n; ++i) {
			ll qwq = BIT::qry(a[i].c);//b,c
			tmp += qwq * (qwq - 1) / 2;
			BIT::add(a[i].c, 1);
		}
		tmp = tmp - tmp1 * 3;
		ans += 1ll * n * (n - 1) * (n - 2) / 6 - tmp - tmp1;
	}
	printf("%lld\n", ans);
}

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

int main() {
	freopen("subset.in", "r", stdin);
	freopen("subset.out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; ++i) {
		a[i].a = read();
	}
	for(int i = 1; i <= n; ++i) {
		a[i].b = read();
	}
	for(int i = 1; i <= n; ++i) {
		a[i].c = read();
	}
	solve();
	return 0;
}

B

差分,b相当于直接单点修改然后前缀和

紧接着我们只对于这样的点对处理:xx,以及x ⊕ kx~\oplus~k,同时钦定左端点为x,然后右端点取值为x⊕kx \oplus k

不难发现这样子之后所有有用的左右端点就单独被留下了,然后考虑简化条件[st,en][st,en]

拆开询问有

  1. [1,R][1,R][L,R][L,R]加上W

  2. [1,st−1][1,st-1][L,R][L,R]减去W

  3. 左端点st之前,右端点在st~en的[L,R][L,R]减去W

前两类都可以直接挂在右端点上处理等价于前缀加

具体的,所有R要加上前缀所有L个数的权值

然后所有的L要加上后缀所有R的对应权值和,这个可以后缀和也很简单

第三类好的是我们已经被st分开了,可以考虑此时也只有一维信息,对于左端点,会被算贡献的是区间[L,R][L,R]中R的数量,他们会产生个数*w的总代价,然后对于左端点小于L的那些的就会被贡献上

对于每个R,也相当于有多少是[1,st][1,st]里的左端点,同时这个右端点要在st后面,但是也好处理,因为此时我们可以直接差分前缀和统计了

最后枚举权值之后就可以做了,复杂度为O(26∗(n+m))O(2^6*(n+m))

考虑一种和权值无关的做法,把操作离线,然后按照en大小排序qR=xqR=x

倒序枚举右端点,每次把en≥Ren\geq R加入,令[st,n][st,n]加上w,w和左端点有关

然后枚举所有满足pL=k⊕xpL=k\oplus x,且≤R\leq R,然后得到对应的值进行修改即可,注意我们要离散化啊

考虑这个区间修改的复杂度,应该能做到O(m)O(\sqrt m),使得每次查询的复杂度为O(1)O(1)

复杂度是O(n2)O(n^2),原因是相同的L可能太多...

所以我们考虑按照有的L的大小进行讨论,设立阈值k

如果太大,大于k的话直接算法1就能有O(n+m)O(n+m),一共有O(nk(n+m))O(\frac{n}{k}(n+m))次,当k取n\sqrt n最好,复杂度为O((n+m)n)O((n+m)\sqrt{n})

实际写起来你会发现第二部分常数相当大,所以可以适当选取1.75倍的n\sqrt n作为块大小...这样最快

我还稍稍卡了卡常数,但是其实没什么意思,因为本题时限是在太宽了,随便跑....

这类题我们应该用两种算法都实现一次暴力,再拼起来就好很多!

分块注意两端点在一块内要暴力修改别改错乐...

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define vi vector<int>
#define ll long long
#define pb push_back
using namespace std;
const int MAXN = 6e5 + 7;
const int P = (1 << 30);
const int B = 600;
int n, m, k;
int a[MAXN], c[MAXN], pre[MAXN], vis[MAXN], siz[MAXN];

struct rec {
	int l, r, w;
	bool operator<(const rec &x)const {
		return r < x.r;
	}
} g[MAXN];

inline int add(int x, int y) {
	x += y;
	if(x >= P)x -= P;
	if(x < 0)x += P;
	return x;
}

namespace CDC {
	int L[MAXN], R[MAXN], bel[MAXN], tot, B;
	ll b[MAXN], tag[MAXN];
	inline void init() {
		B = sqrt(n) + 1; //别是1啊
		tot = 1;
		L[tot] = 1;
		for(int i = 1; i <= n; ++i) {
			if(i % B == 0) {
				R[tot] = i - 1;
				++tot;
				L[tot] = i;
			}
			bel[i] = tot;
		}
		R[tot] = n;
	}
	inline void upd(int x, int l, int r, int y) {
		for(int i = L[x]; i <= R[x]; ++i)
			b[i] = add(b[i], tag[x]);
		tag[x] = 0;
		for(int i = l; i <= r; ++i)
			b[i] = add(b[i], y); //推平了
	}
	inline void mdf(int l, int r, int q) {
		upd(bel[l], l, min(R[bel[l]], r), q);
		if(bel[l] != bel[r])
			upd(bel[r], L[bel[r]], r, q);
		for(int i = bel[l] + 1; i <= bel[r] - 1; ++i)
			tag[i] = add(tag[i], q);
		return ;
	}
	inline ll qry(int l) {//单点查询
		return add(tag[bel[l]], b[l]);
	}
};
vi v;

ll b[MAXN];
inline int getid(int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin();
}

inline void _init() {
	sort(g + 1, g + m + 1);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	pre[0] = -1;
	for(int i = 1; i <= (int)v.size() + 1; ++i)vis[i] = -1;
	for(int i = 1; i <= n; ++i) {
		pre[i] = vis[getid(a[i])];
		if(pre[i] != -1)
			siz[i] = siz[pre[i]] + 1;//多了一层
		vis[getid(a[i])] = i;
	}
	CDC::init();
	return ;
}

int cb[MAXN], ca[MAXN], rc, vist[MAXN], pL[MAXN], sR[MAXN], cb2[MAXN];

inline void init2() {
	for(int i = 1; i <= m; ++i) {
		cb2[g[i].l] = add(cb2[g[i].l], g[i].w);//第一二类
		cb2[g[i].r + 1] = add(cb2[g[i].r + 1], P - g[i].w);
	}
	for(int i = 1; i <= n; ++i)cb2[i] = add(cb2[i], cb2[i - 1]);
}

inline void solve2() {
	for(int i = 0; i <= n; ++i) {
		if(i != 0)
			pL[i] = pL[i - 1];
		if(a[i] == rc) //左端点
			pL[i]++;
		if(a[i] == (rc ^ k))
			b[i + 1] = add(b[i + 1], P - 1ll * cb2[i] * pL[i] % P); //计数
	}
	for(int i = n; i >= 0; --i) {
		sR[i] = sR[i + 1] + (a[i] == (rc ^ k));
		ca[i] = (a[i] == (rc ^ k)) * cb2[i];
		ca[i] = add(ca[i + 1], ca[i]);
		if(a[i] == rc)
			b[i + 1] = add(b[i + 1], ca[i]); //左端点...
	}
	for(int i = 0; i <= n + 1; ++i)ca[i] = cb[i] = 0;
	for(int i = 1; i <= m; ++i) {//减去
		ca[g[i].l] = add(ca[g[i].l], P - 1ll * pL[g[i].l - 2] * g[i].w % P);
		ca[g[i].r + 1] = add(ca[g[i].r + 1], 1ll * pL[g[i].l - 2] * g[i].w % P);
		cb[0] = add(cb[0], P - 1ll * (sR[g[i].l] - sR[g[i].r + 1]) * g[i].w);
		cb[g[i].l - 1] = add(cb[g[i].l - 1], 1ll * (sR[g[i].l] - sR[g[i].r + 1]) * g[i].w);
	}
	for(int i = 1; i <= n; ++i) {
		ca[i] = add(ca[i], ca[i - 1]);
		if(a[i] == (rc ^ k))
			b[i + 1] = add(b[i + 1], P - ca[i]);
	}
	for(int i = 0; i <= n; ++i) {
		if(i != 0)
			cb[i] = add(cb[i], cb[i - 1]);
		if(a[i] == rc)
			b[i + 1] = add(b[i + 1], cb[i]);
		ca[i] = 0; pL[i] = 0; sR[i] = 0;
	}
	for(int i = 0; i <= n; ++i)cb[i] = 0;
	ca[n + 1] = cb[n + 1] = sR[n + 1] = 0;
	return ;
}


inline void solve() {
	int pm = m;
	for(int i = n; i >= 1; --i) {
		while(g[pm].r == i) {
			CDC::mdf(g[pm].l, g[pm].r, g[pm].w);
			--pm;
		}
		ll q = vis[getid(a[i] ^ k)];
		if(!vist[getid(a[i])]) {//这个值做右端点已经被处理过了
			if(siz[q] < B) {
				for(; q != -1; q = pre[q]) {
					b[q + 1] = add(b[q + 1], CDC::qry(q + 1));
					b[i + 1] = add(b[i + 1], P - CDC::qry(q + 1));
				}
			} else {
				vist[getid(a[i])] = 1;
				rc = a[i] ^ k;
				solve2();//冲
			}
		}
		vis[getid(a[i])] = pre[i];//跳回去
	}
	for(int i = 1; i <= n; ++i)b[i] = add(b[i], b[i - 1]);
	for(int i = 1; i <= n; ++i)printf("%lld ", b[i]);
	return ;
}

signed main() {
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &k);
	v.pb(0);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		a[i] ^= a[i - 1];
		v.pb(a[i]);
		v.pb(a[i]^k);
	}
	for(int i = 1; i <= m; ++i)scanf("%d%d%d", &g[i].l, &g[i].r, &g[i].w);
	init2();
	_init();
	solve();
	return 0;
}

C

可以绕着一个点,旋转卡壳

所以这道题就咕掉了

771. 「分块算法」历史序列

这道题在最后半行前都是友好的吉如一线段树

考虑分块,然后第二个操作我们还是利用势能,记录区间最大值是什么,然后观察到有负数哎....

但是说如果有一刻一些数达到了相同的最大值还是可以同一批次处理的...

所以还是可行的??

Powered by Gridea RSS