\(\text{Problem}\)

维护一个序列

支持插入一个数，区间加，询问区间平方和

\(\text{Solution}\)

平衡树很模板的题了

考场打 \(fhq-treap\) 毫无悬念过了

读入有负数，快读注意！

打完之后发现有模数？

狂改代码，无脑乱加模，代码直接丑了

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <ctime>

using namespace std;

const int N = 1e5, P = 7459;

int n, m, rt;

struct node{

	int ls, rs, rnd, sz, val, s1, s2, tg;

}tr[N * 2 + 5];

void read(int &x)

{

	x = 0; int f = 1; char ch = getchar();

	while (!isdigit(ch)) f = (ch == '-' ? -1 : f), ch = getchar();

	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();

	x *= f;

}

void update(int p)

{

	tr[p].sz = tr[tr[p].ls].sz + tr[tr[p].rs].sz + 1;

	tr[p].s1 = (tr[tr[p].ls].s1 + tr[tr[p].rs].s1 + tr[p].val) % P;

	tr[p].s2 = (tr[tr[p].ls].s2 + tr[tr[p].rs].s2 + tr[p].val * tr[p].val % P) % P;

}

int new_node(int v)

{

	static int tot = 0;

	tr[++tot] = node{0, 0, rand(), 1, v, v, v * v % P, 0};

	return tot;

}

void pushdown(int p)

{

	if (!p || !tr[p].tg) return;

	long long v = tr[p].tg;

	if (tr[p].ls)

	{

		tr[tr[p].ls].s2 += v * v % P * tr[tr[p].ls].sz % P + v * 2 * tr[tr[p].ls].s1 % P;

		tr[tr[p].ls].s1 += v * tr[tr[p].ls].sz % P, tr[tr[p].ls].tg += v, tr[tr[p].ls].val += v;

		tr[tr[p].ls].s2 %= P, tr[tr[p].ls].s1 %= P, tr[tr[p].ls].tg %= P, tr[tr[p].ls].val %= P;

	}

	if (tr[p].rs)

	{

		tr[tr[p].rs].s2 += v * v % P * tr[tr[p].rs].sz % P + v * 2 * tr[tr[p].rs].s1 % P;

		tr[tr[p].rs].s1 += v * tr[tr[p].rs].sz % P, tr[tr[p].rs].tg += v, tr[tr[p].rs].val += v;

		tr[tr[p].rs].s2 %= P, tr[tr[p].rs].s1 %= P, tr[tr[p].rs].tg %= P, tr[tr[p].rs].val %= P;

	}

	tr[p].tg = 0;

}

void split(int p, int k, int &x, int &y)

{

	if (!p) x = y = 0;

	else{

		pushdown(p);

		if (k <= tr[tr[p].ls].sz) y = p, split(tr[p].ls, k, x, tr[p].ls);

		else x = p, split(tr[p].rs, k - tr[tr[p].ls].sz - 1, tr[p].rs, y);

		update(p);

	}

}

int merge(int x, int y)

{

	if (!x || !y) return x | y;

	pushdown(x), pushdown(y);

	if (tr[x].rnd < tr[y].rnd)

	{

		tr[x].rs = merge(tr[x].rs, y);

		update(x); return x;

	}

	else{

		tr[y].ls = merge(x, tr[y].ls);

		update(y); return y;

	}

}

inline void insert(int x, int y)

{

	int a, b;

	x = (x + P) % P, split(rt, y - 1, a, b);

	rt = merge(merge(a, new_node(x)), b);

}

void add(int l, int r, long long x)

{

	int a, b, c, d;

	x = (x + P) % P, split(rt, r, a, b), split(a, l - 1, c, d);

	tr[d].s2 += x * x % P * tr[d].sz % P + x * 2 * tr[d].s1 % P;

	tr[d].s1 += x * tr[d].sz % P, tr[d].tg += x, tr[d].val += x;

	tr[d].s2 %= P, tr[d].s1 %= P, tr[d].tg %= P, tr[d].val %= P;

	rt = merge(merge(c, d), b);

}

int query(int l, int r)

{

	int a, b, c, d;

	split(rt, r, a, b), split(a, l - 1, c, d);

	int res = tr[d].s2;

	rt = merge(merge(c, d), b);

	return res;

}

int main()

{

	srand(time(0)), read(n);

	char op[10]; int l, r, x;

	for(int i = 1; i <= n; i++) read(x), insert(x, i);

	read(m);

	for(int i = 1; i <= m; i++)

	{

		scanf("%s", op), read(l), read(r);

		if (op[0] == 'I') insert(r, l);

		else if (op[0] == 'A') read(x), add(l, r, x);

		else printf("%d\n", query(l, r));

	}

}

巴特西

JZOJ 4216.平方和

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章