【BZOJ2752】【Luogu P2221】 [HAOI2012]高速公路

不是很难的一个题目。正确思路是统计每一条边被经过的次数，但我最初由于习惯直接先上了一个前缀和再推的式子，导致极其麻烦难以写对而且会爆\(longlong\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 100000 + 5;

#define ls (p << 1)

#define rs (p << 1 | 1)

#define mid ((l + r) >> 1)

#define int long long

int n, m, sum1, sum2, sum3;

struct Segment_Tree {

    int tag[N << 2], s1[N << 2], s2[N << 2], s3[N << 2];

	Segment_Tree () {

        memset (s1, 0, sizeof (s1));

        memset (s2, 0, sizeof (s2));

        memset (s3, 0, sizeof (s3));

        memset (tag, 0, sizeof (tag));

    }

    void push_up (int p) {

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

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

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

    }

    int F1 (int x, int y) {return y - x + 1;}  // \sum_{i = x} ^ {y} i ^ 0

    int F2 (int x, int y) {return (x + y) * (y - x + 1) / 2;} // \sum_{i = x} ^ {y} i ^ 1

    int F3 (int x, int y) {

		x = x - 1;

		int w1 = x * (x + 1) * (2 * x + 1) / 6;

		int w2 = y * (y + 1) * (2 * y + 1) / 6;

		return w2 - w1;

	} // \sum_{i = x} ^ {y} i ^ 2

    void work (int p, int l, int r, int val) {

		s1[p] += F1 (l, r) * val;

		s2[p] += F2 (l, r) * val;

		s3[p] += F3 (l, r) * val;

		tag[p] += val;

	}

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

    	work (ls, l, mid + 0, tag[p]);

    	work (rs, mid + 1, r, tag[p]);

    	tag[p] = 0;

	}

	void modify (int nl, int nr, int w, int l = 1, int r = n, int p = 1) {

		if (nl <= l && r <= nr) {

			work (p, l, r, w);

			return;

		}

		push_down (p, l, r);

		if (nl <= mid) modify (nl, nr, w, l, mid, ls);

		if (mid < nr) modify (nl, nr, w, mid + 1, r, rs);

		push_up (p); return;

	}

    void query (int nl, int nr, int l = 1, int r = n, int p = 1) {

        if (nl <= l && r <= nr) {

        	sum1 += s1[p];

        	sum2 += s2[p];

        	sum3 += s3[p];

        	return;

		}

        push_down (p, l, r);

        if (nl <= mid) query (nl, nr, l, mid, ls);

        if (mid < nr) query (nl, nr, mid + 1, r, rs);

        push_up (p); return;

    }

}tr; // 维护 \sum_{x = L}^{R} sumd(x) 

int gcd (int x, int y) {

	return y ? gcd (y, x % y) : x;

}

signed main () {

	freopen ("data.in", "r", stdin);

	cin >> n >> m;

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

		char opt; int l, r, v;

		cin >> opt;

		if (opt == 'C') {

			cin >> l >> r >> v; r--;

			tr.modify (l, r, v);

		} else {

			cin >> l >> r; r--;

			sum1 = sum2 = sum3 = 0;

			tr.query (l, r);

			int w1 = (r - l + 1 - r * l);

			int w2 = l + r;

			int w3 = -1;

			int upp = w1 * sum1 + w2 * sum2 + w3 * sum3;

			int dwn = (r - l + 2) * (r - l + 1) / 2;

			int d = gcd (upp, dwn); upp /= d, dwn /= d;

			cout << upp << "/" << dwn << endl;

		}

	}

}

巴特西

【BZOJ2752】【Luogu P2221】 [HAOI2012]高速公路

最新文章

热门文章