依旧是水的一匹的考试…三道原题…两道写过…

T1

begin: 7:30
裸网络流…啥都没改差评
码了30min+-好菜啊QAQ明明是个小模板…

T2

又是原题调了好久…_(:з」∠)_我凉了啊QAQ
写了1h终于过样例了…明明当初做的时候是1A啊QAQ

T3

9:00…
woc这个题太™恶心了…虽然一眼就是个线段树裸题…但是…太恶心了…写main函数我就写了108行…加上我的垃圾字符串…凉凉….
10:00Maya我终于写完main函数辣QAQ! 一看时间觉得非常不稳啊赶紧码码码…
30min线段树写完了…
诶怎么错了啊QAQ
原先好像写过一发线段树就是这种区间覆盖的…然后标记太乱就一直WA…现在也还晾在那…
调试…mdpush_down的时候区间覆盖完了就应该把区间翻转去掉…就这样调了1h….凉凉
不管怎样收卷前调出样例了hin开心…

事后…

Maya我的调试忘改了…为了调试方便我数组就开了…5…然后T3就凉了…挂成10分样例分…md$n^2$暴力都比我强…
然后改过来发现崩溃了…一看数据md怎么有这种数据…

S [3,5]
S [3,5]
U [5,5)
U (5,5)

woc你家区间这么写mmp…特判了一下

if (le > ri)
    return ;

然后还是WAWAWA…手动输了数据全™对了??? 交到b站也A了??? 似乎是Cena的锅…

癌…因为CTL的集合书写和没删调试痛失AK机会…QAQ

代码 && 简单介绍

T1

有必要说嘛?

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
#define LINF (0x7ffffffffll)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define RS(dq) (((dq) << 1) | 1)
#define LS(dq) ((dq) << 1)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define LL long long
using namespace std; // 答案需要使用ll 
struct edg
{
    int from, to, next, cap, flow;
    edg() {}
    edg(int fr, int t, int ne, int ca, int fl): from(fr), to(t), next(ne), cap(ca), flow(fl) {}
}b[MAXM << 1];
int g[MAXN], cntb, dis[MAXN], s, t;
LL ans;
inline void adn(int, int, int);
LL dinic(int, LL);
int bfs();
void solve();
int main()
{
//#define Debug
#ifndef Debug
    freopen("ditch.in" ,"r", stdin);
    freopen("ditch.out", "w", stdout);
#endif
    int m, n;
    scanf("%d%d", &m, &n);
    s = 1, t = n;
    for (int i = 1; i <= m; i++)
    {
        int srx, sry, srz;
        scanf("%d%d%d", &srx, &sry, &srz);
        adn(srx, sry, srz);
        adn(sry, srx, 0);
    }
    solve();
    printf("%lld", ans);
    return 0;
}
inline void adn(int from, int to, int cap)
{
    b[++cntb] = edg(from, to, g[from], cap, 0);
    g[from] = cntb;
}
LL dinic(int dq, LL maxf)
{
    if (dq == t ||  (!maxf))
        return maxf;
    LL re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if ((dis[b[i].to] == dis[dq] + 1) && b[i].cap > b[i].flow)
        {
            LL zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            re += zl;
            maxf -= zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
        }
    }
    return re;
}
int bfs()
{
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            if ((!dis[b[i].to]) && b[i].cap > b[i].flow)
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
        }
    }
    return dis[t];
}
void solve()
{
    while (bfs())
        ans += dinic(s, LINF);
}

/*
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
*/

T2

裸的树链剖分…考模板×原题是要干甚啊…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXQ (100000 + 5)
#define MNULL (MAXN - 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define RS(dq) (((dq) << 1) | 1)
#define LS(dq) ((dq) << 1)
#define rev(i) ((((i) - 1) ^ 1) + 1)
const int root = 0;
using namespace std;
struct edg
{
    int from, to, next;
    edg() {}
    edg(int fr, int t, int ne): from(fr), to(t), next(ne) {}
} tb[MAXN << 1];
int tg[MAXN], cntb;
struct tnode
{
    int fa, hs, sum, top, begin, end, deep;
} ta[MAXN];
struct node
{
    int le, ri, zh, lazy;
} b[MAXN << 3];
int n, a[MAXN], cnta;
void js(int, int, int); //
void xg(int, int, int, int); //
int cx(int, int, int); //
inline void push_up(int); 
inline void push_down(int);
inline void adn(int, int); //
void init(int, int); // 
void dfs(int); // 
int solve(int);
int main()
{
//#define Debug
#ifndef Debug
    freopen("manager.in" ,"r", stdin);
    freopen("manager.out", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int srx;
        scanf("%d", &srx);
        adn(srx, i);
    }
    ta[root].fa = root, ta[root].top = root;
    init(root, 1);
    dfs(root);
    js(1, 1, n);
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        char sre[20 + 5];
        int srx;
        scanf("%s%d", sre, &srx);
        if (sre[0] == 'u')
        {
            printf("%d\n", cx(1, ta[srx].begin, ta[srx].end));
            xg(1, ta[srx].begin, ta[srx].end, 0);
        }
        else
            printf("%d\n", ta[srx].deep - solve(srx));
    }
    return 0;
}
inline void adn(int from, int to)
{
    tb[++cntb] = edg(from, to, tg[from]);
    tg[from] = cntb;
}
void init(int dq, int deep)
{
    ta[dq].deep = deep;
    ta[dq].sum = 1;
    ta[dq].hs =     MNULL;
    for (int i = tg[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa)
        {
            ta[tb[i].to].fa = dq;
            init(tb[i].to, deep + 1);
            if (ta[ta[dq].hs].sum < ta[tb[i].to].sum)
                ta[dq].hs = tb[i].to;
            ta[dq].sum += ta[tb[i].to].sum;
        }
    }
}
/*
struct tnode
{
    int fa, hs, sum, top, begin, end, deep;
} ta[MAXN];
*/
void dfs(int dq)
{
    ta[dq].begin = ++cnta;
    if (ta[dq].hs != MNULL)
    {
        ta[ta[dq].hs].top = ta[dq].top;
        dfs(ta[dq].hs);
    }
    for (int i = tg[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
        {
            ta[tb[i].to].top = tb[i].to;
            dfs(tb[i].to);
        }
    }
    ta[dq].end = cnta;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    b[dq].lazy = 2;
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh)
{
    if(b[dq].lazy != 2)
        push_down(dq);
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].lazy = zh;
        b[dq].zh = (ri - le + 1) * zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        xg(RS(dq), le, ri, zh);
    else if (ri <= mi)
        xg(LS(dq), le, ri, zh);
    else
        xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    push_up(dq);
}
int cx(int dq, int le, int ri)
{
    if (b[dq].lazy != 2)
        push_down(dq);
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        return cx(RS(dq), le, ri);
    else if (ri <= mi)
        return cx(LS(dq), le, ri);
    else
        return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
inline void push_up(int dq)
{ b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh; }
inline void push_down(int dq)
{
    int x;
    b[LS(dq)].lazy = b[RS(dq)].lazy = x =b[dq].lazy;
    b[LS(dq)].zh = (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
    b[RS(dq)].zh = (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
    b[dq].lazy = 2;
}
int solve(int x)
{
    int re = 0;
    while (ta[x].top != root)
    {
        re += cx(1, ta[ta[x].top].begin, ta[x].begin);
        xg(1, ta[ta[x].top].begin, ta[x].begin, 1);
        x = ta[ta[x].top].fa;
    }
    re += cx(1, ta[ta[x].top].begin, ta[x].begin);
    xg(1, ta[ta[x].top].begin, ta[x].begin, 1);
    return re;
}

/*
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
*/

T3

把每个数分成两个点, 一个是数本身, 一个是这个数和他右边那个数之间的开区间
即:
开闭区间的实现方法

然后集合间计算的实现可以看注释

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#define MAXN (80000 + 1)
#define MAXQ (70000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define wz(x) (((x) << 1) + 2)
#define ln(x) (((x) << 1) + 1)
#define rn(x) (((x) << 1) + 3)
#define swap(a, b) {int t = a; a = b; b = t;}
#define pii pair<int, int>
#define mkp(a, b) make_pair(a, b)
using namespace std;
struct node
{
    int zh1, zh0, le, ri;
    int lazy01;
    bool lazyf;
} b[MAXN << 5];
// 每个数要拆成两个来确定开闭区间
// U: 修改给定区间为1
// I: 修改非给定区间为0
// D: 修改给定区间为0
// C: 修改非给定区间为0, 给定区间内取反
// S: 给定区间取反
void js(int, int, int);
void xg(int, int, int, int);
// 0: ->0
// 1: ->1
// 2: 0->1, 1->0
int cx(int, int);
void push_down(int);
void push_up(int);
void sti(string&, int&, int&);
int main()
{
//#define Debug
#ifndef Debug
    freopen("interval.in" ,"r", stdin);
    freopen("interval.out", "w", stdout);
#endif
    js(1, 1, (MAXN << 2));
    string sre, sr;
    while (cin >> sre)
    {
        cin >> sr;
        bool zb = (sr[0] == '['), yb = (sr[sr.length() - 1] == ']');
        int lex, rix;
        sti(sr, lex, rix);
        int dql = (zb ? wz(lex) : rn(lex)), dqr = (yb ? wz(rix) : ln(rix));
        if (sre == "U")
            xg(1, dql, dqr, 1);
        if (sre == "D")
            xg(1, dql, dqr, 0);
        if (sre == "C" || sre == "S")
            xg(1, dql, dqr, 2);
        if (sre == "I" || sre == "C")
        {
            dql = (zb ? rn(lex - 1) : wz(lex)), dqr = (yb ? ln(rix + 1) : wz(rix));
            if (dql > 0)
                xg(1, 1, dql, 0);
            if (dqr < (MAXN << 2))
                xg(1, dqr, (MAXN << 2) - 1, 0);
        }
    }
    bool ok = false;
    vector<pii> ans; // 1: self, 2: right
    for (int i = 0; i < MAXN; i++)
    {
        if (cx(1, wz(i)))
            ans.push_back(mkp(i, 1)), ok = true;
        if (cx(1, rn(i)))
            ans.push_back(mkp(i, 2)), ok = true;
    }
    if (!ok)
    {
        puts("empty set");
        return 0;
    }
    int n = ans.size();
    bool last = false;
    for (int i = 0; i < n; i++)
    {
        if (ans[i].second == 1)
        {
            if (!last)
                cout << "[" << ans[i].first << ",", last = true;
            if (i == n - 1 || ans[i + 1].first != ans[i].first)
                cout << ans[i].first << "] ", last = false;
        }
        else if (ans[i].second== 2)
        {
            if (!last)
                cout << "(" << ans[i].first << ",", last = true;
            if (i == n - 1 || (ans[i + 1].second != 1 || ans[i + 1].first != ans[i].first + 1))
                cout << ans[i].first + 1 << ") ", last = false;
        }
    }
    return 0;
}
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    b[dq].lazy01 = 2, b[dq].lazyf = false;
    if (le == ri)
    {
        b[dq].zh0 = 1;
        return ;
    }
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
    push_up(dq);
}
// 0: ->0
// 1: ->1
// 2: 0->1, 1->0
void xg(int dq, int le, int ri, int zh)
{
    if (le > ri)
        return ;
    if (b[dq].lazy01 != 2 || b[dq].lazyf)
        push_down(dq);
    if (b[dq].le == le && b[dq].ri == ri)
    {
        if (zh < 2)
        {
            b[dq].lazy01 = zh;
            b[dq].zh1 = (b[dq].ri - b[dq].le + 1) * zh;
            b[dq].zh0 = (b[dq].ri - b[dq].le + 1) - b[dq].zh1;
        }
        else
        {
            b[dq].lazyf = !b[dq].lazyf;
            swap(b[dq].zh0, b[dq].zh1);
        }
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (ri <= mi)
        xg(LS(dq), le, ri, zh);
    else if (le > mi)
        xg(RS(dq), le, ri, zh);
    else
        xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    push_up(dq);
}
int cx(int dq, int wz)
{
    if (b[dq].lazy01 != 2 || b[dq].lazyf)
        push_down(dq);
    if (b[dq].le == b[dq].ri && b[dq].le == wz)
        return b[dq].zh1;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz <= mi)
        return cx(LS(dq), wz);
    else
        return cx(RS(dq), wz);
}
void sti(string& s, int& le, int& ri)
{
    int wz = 1;
    le = ri = 0;
    while (s[wz] != ',')
        le = (le << 1) + (le << 3) + s[wz++] - '0';
    ++wz;
    while (s[wz] <= '9' && s[wz] >= '0')
        ri = (ri << 1) + (ri << 3) + s[wz++] - '0';
}
void push_up(int dq)
{
    b[dq].zh0 = b[LS(dq)].zh0 + b[RS(dq)].zh0;
    b[dq].zh1 = b[LS(dq)].zh1 + b[RS(dq)].zh1;
}
void push_down(int dq)
{
    if (b[dq].lazy01 != 2)
    {
        int x;
        b[RS(dq)].lazy01 = b[LS(dq)].lazy01 = x = b[dq].lazy01;
        b[RS(dq)].zh1 = x * (b[RS(dq)].ri - b[RS(dq)].le + 1);
        b[RS(dq)].zh0 = (b[RS(dq)].ri - b[RS(dq)].le + 1) - b[RS(dq)].zh1;
        b[LS(dq)].zh1 = x * (b[LS(dq)].ri - b[LS(dq)].le + 1);
        b[LS(dq)].zh0 = (b[LS(dq)].ri - b[LS(dq)].le + 1) - b[LS(dq)].zh1;
        b[LS(dq)].lazyf = b[RS(dq)].lazyf = false;
    }
    if (b[dq].lazyf)
    {
        b[LS(dq)].lazyf = !b[LS(dq)].lazyf;
        b[RS(dq)].lazyf = !b[RS(dq)].lazyf;
        swap(b[LS(dq)].zh0, b[LS(dq)].zh1);
        swap(b[RS(dq)].zh0, b[RS(dq)].zh1);
    }
    b[dq].lazy01 = 2;
    b[dq].lazyf = false;
}

/*
U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

(2, 3)

1 2 3 4 5 6 7 8 9 0 1 2 3
0 0 0 0 0 0 0 0 0 0 0 0 0
  0   1   2   3   4   5

0 0 0 1 1 1 1 1 1 1 1 1 0
0 0 0 1 1 1 1 0 1 1 1 1 0
0 0 0 1 1 0 0 1 0 0 1 1 0
0 0 0 0 0 1 1 0 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 


// 每个数要拆成两个来确定开闭区间
// U: 修改给定区间为1
// I: 修改非给定区间为0
// D: 修改给定区间为0
// C: 修改非给定区间为0, 给定区间内取反
// S: 给定区间取反
*/

By 被奶死的 Cansult