NIO9102 落雨大

按理来说题解里不应该包含模板，只不过这也不是什么官方题解，我就懒得换成正常写法了。

#ifndef OUUAN
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#endif
#include<bits/stdc++.h>

#define int LoveLive
//#define FAST_IOSTREAM 1

#define For(i,l,r)for(int i=(l),i##end=(r);i<=i##end;++i)
#define FOR(i,r,l)for(int i=(r),i##end=(l);i>=i##end;--i)
#define SON(i,u)for(int i=head[u];i;i=nxt[i])
#define ms(a,x)memset(a,x,sizeof(a))
#define fi first
#define se second
#define pq priority_queue
#define pb emplace_back
#define isinf(x)(x>=INF?-1:x)
#define DEBUG(x)cerr<<(#x)<<":"<<x<<endl
using namespace std;typedef long long LoveLive;typedef pair<int,int>pii;typedef vector<int>vi;
#ifdef int
const int INF=0x3f3f3f3f3f3f3f3fll;
#else
const int INF=0x3f3f3f3f;
#endif
const double eps=1e-9;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int randint
(int l,int r){return(int)rng()%(r-l+1)+l;}
#ifdef FAST_IOSTREAM
#define br cout<<'\n'
#define sp cout<<' '
long long read(){long long x;cin>>x;return x;}template<typename T>void read(T&x){cin>>x;}template<typename
T>void write(const T&x){cout<<x;}
#else
#define br putchar('\n')
#define sp putchar(' ')
template<typename T>typename enable_if<!is_integral<T>::value,void>::type read(T&x){cin>>x;}long long
read(){char c;long long out=0,f=1;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c
=getchar();}for(;isdigit(c);c=getchar())out=(out<<3)+(out<<1)+c-'0';return out*f;}template<typename T
>typename enable_if<is_integral<T>::value,T>::type read(T&x){char c;T f=1;x=0;for(c=getchar();!isdigit
(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';
return x*=f;}char read(char&x){for(x=getchar();isspace(x);x=getchar());return x;}double read(double
&x){scanf("%lf",&x);return x;}void read(char*x){scanf("%s",x);}template<typename T>typename enable_if
<!is_integral<T>::value,void>::type write(const T&x){cout<<x;}template<typename T>typename enable_if<
is_integral<T>::value,void>::type write(const T&x){if(x<0){putchar('-');write(-x);return;}if(x>9)write
(x/10);putchar(x%10+'0');}void write(const char&x){putchar(x);}void write(const double&x){printf("%.10lf"
,x);}void write(const char*x){printf("%s",x);}
#endif
template<typename T,typename...Args>void read(T&x,Args&...args){read(x);read(args...);}template<typename
...Args>void read(char*x,Args&...args){read(x);read(args...);}template<typename OutputIt,typename=typename
enable_if<is_same<output_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value ||(
is_base_of<forward_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value&&!is_const
<OutputIt>::value)>::type>void read(OutputIt __first,OutputIt __last){for(;__first!=__last;++__first)
read(*__first);}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename
iterator_traits<InputIt>::iterator_category>::value>::type>void wts(InputIt __first,InputIt __last){
for(;__first!=__last;++__first){write(*__first);sp;}}template<typename InputIt,typename=typename enable_if
<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void
wtb(InputIt __first,InputIt __last){for(;__first!=__last;++__first){write(*__first);br;}}void wts(const
char*x){write(x);sp;}void wtb(const char*x){write(x);br;}void wte(const char*x){write(x);exit(0);}template
<typename T>void wts(const T&x){write(x);sp;}template<typename T>void wtb(const T&x){write(x);br;}template
<typename T>void wte(const T&x){write(x);exit(0);}template<typename...Args>void wts(const char*x,Args
...args){wts(x);wts(args...);}template<typename...Args>void wtb(const char*x,Args...args){wts(x);wtb(
args...);}template<typename...Args>void wte(const char*x,Args...args){wts(x);wte(args...);}template<typename
T,typename...Args>void wts(const T&x,Args...args){wts(x);wts(args...);}template<typename T,typename...
Args>void wtb(const T&x,Args...args){wts(x);wtb(args...);}template<typename T,typename...Args>void wte
(const T&x,Args...args){wts(x);wte(args...);}template<typename T>inline bool up(T&x,const T&y){return
x<y?x=y,1:0;}template<typename T>inline bool dn(T&x,const T&y){return y<x?x=y,1:0;}

const int N = 100010;
const int M = 200010;

int n, m, a, b, c, id[M];

struct Edge
{
	int u, v, p, q, f;
	bool operator<(const Edge & b) const
	{
		return q > b.q;
	}
} e[M];

struct Point
{
	int x, y;
	Point(int j = 0): x(2 * a * e[j].p), y(a * e[j].p * e[j].p + b * e[j].p + e[j].q + e[j].f) {}
	friend bool cmp(const Point & a1, const Point & a2, const Point & a3)
	{
		if (a1.x == a2.x) return a1.y < a2.y;
		return (a1.y - a3.y) * (a2.x - a3.x) >= (a2.y - a3.y) * (a1.x - a3.x);
	}
	int cal(int k) const { return y - k * x; }
};

struct Deque
{
	vector<Point> q;
	int ql, qr;
	Deque()
	{
		q.resize(1);
		ql = 1;
		qr = 0;
	}
	bool empty() const { return ql > qr; }
	void push_back(const Point & x)
	{
		++qr;
		if (q.size() == qr) q.push_back(x);
		else q[qr] = x;
	}
	void cal(int i)
	{
		while (ql < qr && q[ql + 1].cal(e[i].q) <= q[ql].cal(e[i].q)) ++ql;
		e[i].f = q[ql].cal(e[i].q) + a * e[i].q * e[i].q - b * e[i].q + c - e[i].q;
	}
	void insert(const Point & x)
	{
		while (ql < qr && cmp(x, q[qr], q[qr - 1])) --qr;
		push_back(x);
	}
} q[N];

signed main()
{
#ifdef FAST_IOSTREAM
	cin.sync_with_stdio(false);
	cin.tie(0);
#endif
	
	read(n, m, a, b, c);
	
	For (i, 1, m) read(e[i].u, e[i].v, e[i].p, e[i].q);
	++m;
	e[m].u = 0;
	e[m].v = 1;
	e[m].p = 0;
	e[m].q = 0;
	sort(e + 1, e + m + 1);
	
	For (i, 1, m) id[i] = i;
	sort(id + 1, id + m + 1, [](int x, int y) { return e[x].p > e[y].p; });
	int idp = 1;
	
	For (i, 1, m)
	{
		if (e[i].v == n)
		{
			e[i].f = 0;
			continue;
		}
		while (idp <= m && e[id[idp]].p >= e[i].q)
		{
			if (e[id[idp]].f < INF) q[e[id[idp]].u].insert(Point(id[idp]));
			++idp;
		}
		if (q[e[i].v].empty())
		{
			e[i].f = INF;
			continue;
		}
		q[e[i].v].cal(i);
	}
	
	For (i, 1, m) if (e[i].u == 0) wte(e[i].f);
	
	return 0;
}

#include <iostream>
#include <cstdio>
#include <cctype>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int read()
{
    int out = 0;
    char c;
    while (!isdigit(c = getchar()));
    for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
    return out;
}

typedef pair<int, int> pii;

const int N = 200010;
const int INF = 1e9;

int T, n, k, dif, a[N], b[N], ida[N], idb[N], idab[N], pa, pb, pab, fa[N], fb[N]; // dif 是剩余可选择的不一样下标个数，id 是用来排序的，pa，pb，pab 记录用到了第几个值（即当前最大值是 a[pa] 之类的），fa，fb 分别记录 a_i 和 b_i 匹配的数的下标
priority_queue<pii> sa, sb, emptypq; // sa 是 b 已匹配的 a，sb 是 a 已匹配的 b，emptypq 是用来多测清空的

void link(int u, int v) // 匹配两个数
{
    --dif;
    fa[u] = v;
    fb[v] = u;
    if (u == v) --dif; // 去重，否则会在下面三行代码里加两次
    if (fb[u]) ++dif;
    else sb.push(pii(b[u], u));
    if (fa[v]) ++dif;
    else sa.push(pii(a[v], v));
}

void cut(int u, int v) // 断开匹配
{
    ++dif;
    if (fb[u]) --dif;
    if (fa[v]) --dif;
    if (u == v) ++dif; // 去重
    fa[u] = fb[v] = 0;
}

pii geta() // 获取当前剩余的最大 a
{
    while (fa[ida[pa]]) ++pa;
    return pii(a[ida[pa]], ida[pa]);
}

pii getb() // 获取当前剩余的最大 b
{
    while (fb[idb[pb]]) ++pb;
    return pii(b[idb[pb]], idb[pb]);
}

pii getab() // 获取当前剩余的最大 a + b
{
    while (pab <= n && (fa[idab[pab]] || fb[idab[pab]])) ++pab;
    return pii(pab <= n ? a[idab[pab]] + b[idab[pab]] : -INF, idab[pab]);
}

pii getsa() // 获取 b 已选的最大 a
{
    while (!sa.empty() && fa[sa.top().second]) sa.pop();
    return sa.empty() ? pii(-INF, 0) : sa.top();
}

pii getsb() // 获取 a 已选的最大 b
{
    while (!sb.empty() && fb[sb.top().second]) sb.pop();
    return sb.empty() ? pii(-INF, 0) : sb.top();
}

int main()
{
    T = read();

    while (T--)
    {
        pa = pb = pab = 1;
        sa = sb = emptypq;
        memset(fa, 0, sizeof(fa));
        memset(fb, 0, sizeof(fb));

        n = read();
        k = read();
        dif = k - read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        for (int i = 1; i <= n; ++i) b[i] = read();

        for (int i = 1; i <= n; ++i) ida[i] = idb[i] = idab[i] = i;
        sort(ida + 1, ida + n + 1, [](int x, int y){return a[x] > a[y];});
        sort(idb + 1, idb + n + 1, [](int x, int y){return b[x] > b[y];});
        sort(idab + 1, idab + n + 1, [](int x, int y){return a[x] + b[x] > a[y] + b[y];});

        while (k--)
        {
            if (dif) link(geta().second, getb().second);
            else
            {
                pii nab = getab();
                pii na_a = getsa();
                pii na_b = getb();
                pii nb_a = geta();
                pii nb_b = getsb();
                if (nab.first >= na_a.first + na_b.first && nab.first >= nb_a.first + nb_b.first) link(nab.second, nab.second);
                else if (na_a.first + na_b.first >= nb_a.first + nb_b.first)
                {
                    int t = fb[na_a.second];
                    cut(t, na_a.second);
                    link(t, na_b.second);
                    link(na_a.second, na_a.second);
                }
                else
                {
                    int t = fa[nb_b.second];
                    cut(nb_b.second, t);
                    link(nb_a.second, t);
                    link(nb_b.second, nb_b.second);
                }
            }
        }

        long long ans = 0;
        for (int i = 1; i <= n; ++i) ans += (fa[i] ? a[i] : 0) + (fb[i] ? b[i] : 0);
        printf("%lld\n", ans);
    }

    return 0;
}