Cow Tennis Tournament https://codeforces.com/problemset/problem/283/E
感觉这题的难点在于想到求违反条件的三元组..
为什么在自己想的时候没有想到求反面呢!!!!
违反的三元组肯定存在一个人能打败其他两个人, 扫描的过程中用线段树维护一下就好了.
反思: 计数问题: 正难则反 正难则反 正难则反 !!!!
- #include<bits/stdc++.h>
- #define LL long long
- #define LD long double
- #define ull unsigned long long
- #define fi first
- #define se second
- #define mk make_pair
- #define PLL pair<LL, LL>
- #define PLI pair<LL, int>
- #define PII pair<int, int>
- #define SZ(x) ((int)x.size())
- #define ALL(x) (x).begin(), (x).end()
- #define fio iOS::sync_with_stdio(false); cin.tie(0);
- using namespace std;
- const int N = 1e5 + 7;
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- const int mod = 1e9 + 7;
- const double eps = 1e-8;
- const double PI = acos(-1);
- template<class T, class S> inline void add(T& a, S b) {a += b; if(a>= mod) a -= mod;}
- template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a <0) a += mod;}
- template<class T, class S> inline bool chkmax(T& a, S b) {return a <b ? a = b, true : false;}
- template<class T, class S> inline bool chkmin(T& a, S b) {return a> b ? a = b, true : false;}
- int n, k, s[N];
- int cntL[N], cntR[N];
- vector in[N], ot[N];
- #define lson l, mid, rt <<1
- #define rson mid + 1, r, rt <<1 | 1
- struct setmentTree {
- int a[N << 2][2];
- int flip[N << 2];
- inline void pull(int rt) {
- a[rt][0] = a[rt << 1][0] + a[rt << 1 | 1][0];
- a[rt][1] = a[rt << 1][1] + a[rt << 1 | 1][1];
- }
- inline void push(int rt) {
- if(flip[rt]) {
- swap(a[rt << 1][0], a[rt << 1][1]);
- swap(a[rt << 1 | 1][0], a[rt << 1 | 1][1]);
- flip[rt << 1] ^= 1;
- flip[rt << 1 | 1] ^= 1;
- flip[rt] = 0;
- }
- }
- void build(int l, int r, int rt) {
- flip[rt] = 0;
- if(l == r) {
- a[rt][0] = 1;
- a[rt][1] = 0;
- return;
- }
- int mid = l + r>> 1;
- build(lson); build(rson);
- pull(rt);
- }
- void update(int L, int R, int l, int r, int rt) {
- if(R <l || r <L || R < L) return;
- if(L <= l && r <= R) {
- swap(a[rt][0], a[rt][1]);
- flip[rt] ^= 1;
- return;
- }
- push(rt);
- int mid = l + r>> 1;
- update(L, R, lson);
- update(L, R, rson);
- pull(rt);
- }
- PII query(int L, int R, int l, int r, int rt) {
- if(R <l || r <L || R < L) return mk(0, 0);
- if(L <= l && r <= R) return mk(a[rt][0], a[rt][1]);
- push(rt);
- int mid = l + r>> 1;
- PII ret, tmp;
- tmp = query(L, R, lson);
- ret.fi += tmp.fi; ret.se += tmp.se;
- tmp = query(L, R, rson);
- ret.fi += tmp.fi; ret.se += tmp.se;
- return ret;
- }
- } Tree;
- struct Line {
- int l, r;
- } seg[N];
- int main() {
- scanf("%d%d", &n, &k);
- for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
- sort(s + 1, s + 1 + n);
- for(int i = 1; i <= k; i++) {
- int a, b; scanf("%d%d", &a, &b);
- a = lower_bound(s + 1, s + 1 + n, a) - s;
- b = upper_bound(s + 1, s + 1 + n, b) - s - 1;
- seg[i].l = a; seg[i].r = b;
- if(a <= b) {
- in[a].push_back(i);
- ot[b].push_back(i);
- }
- }
- Tree.build(1, n, 1);
- for(int i = 1; i <= n; i++) {
- for(auto &id : in[i]) Tree.update(seg[id].l, seg[id].r, 1, n, 1);
- cntL[i] = Tree.query(1, i - 1, 1, n, 1).fi;
- for(auto &id : ot[i]) Tree.update(seg[id].l, seg[id].r, 1, n, 1);
- }
- Tree.build(1, n, 1);
- for(int i = n; i>= 1; i--) {
- for(auto &id : ot[i]) Tree.update(seg[id].l, seg[id].r, 1, n, 1);
- cntR[i] = Tree.query(i + 1, n, 1, n, 1).se;
- for(auto &id : in[i]) Tree.update(seg[id].l, seg[id].r, 1, n, 1);
- }
- LL ans = 1LL * n * (n - 1) * (n - 2) / 6;
- for(int i = 1; i <= n; i++) {
- ans -= 1LL * cntL[i] * (cntL[i] - 1) / 2;
- ans -= 1LL * cntR[i] * (cntR[i] - 1) / 2;
- ans -= 1LL * cntL[i] * cntR[i];
- }
- printf("%lld\n", ans);
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-3086208.html