考虑网络流求解这类分配问题。

建立源点 $S$，汇点 $T$。令从 $S$ 到 $T$ 的一条路径表示一个奶牛得到了喜欢的食物和饮料。

显然需要对每个食物 $i$ 建立点 $f_i$，对饮料 $j$ 建立点 $d_j$。

食物的点集和饮料的点集显然不能同时连向源点 $S$，不妨对于每个 $f_i,d_j$ 建立 $S \to f_i$ 和 $d_j \to T$ 的容量为 $1$ 的有向边。

如果每个奶牛直接和食物和饮料的集合连边，那么很可能会出现同一个奶牛同时享有多种食物和饮料的情况，然而这时奶牛对最大流的贡献仅为 $1$，求出的最大流却有可能很大。

考虑对其进行限制。对于每个奶牛，建立两个点，两点间连一条容量为 $1$ 的边，这两个点再分别与喜欢的食物和饮料相连，这样就能保证同一个奶牛至多满足一次。

最后直接在建出的图上跑最大流即可。

（代码很丑，见谅）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 20005;
int ver[maxn << 1],nxt[maxn << 1],cap[maxn << 1],head[maxn];
int cnt = -1;
int cur[maxn],level[maxn];
queue <int> q; 
void add(int u,int v,int t) {
    nxt[++ cnt] = head[u];
    ver[cnt] = v;
    cap[cnt] = t;
    head[u] = cnt;
    return ;
}
void AddEdge(int u,int v) {
    add(u , v , 1);
    add(v , u , 0);
    return ;
}
int n;
bool bfs(int s,int t) {
    memset(level , 0 , sizeof(level));
    q.push(s);
    level[s] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u];~ i;i = nxt[i]) {
            int v = ver[i];
            if(!level[v]&&cap[i]) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x,int t,int maxflow) {
    if(x == t||!maxflow)return maxflow;
    int flow = 0,f;
    for(int& i = cur[x];~ i;i = nxt[i]) {
        int v = ver[i];
        if(level[v] == level[x] + 1&&(f = dfs(v , t , min(maxflow , cap[i])))) {
            if(!f) {
                level[v] = 0;
                break ;
            }
            flow += f;
            maxflow -= f;
            cap[i] -= f;
            cap[i ^ 1] += f;
            if(!maxflow)break;
        }
    }
    return flow;
}
int Dinic(int s,int t) {
    int flow = 0;
    while(bfs(s , t)) {
        memcpy(cur , head , sizeof(cur));
        flow += dfs(s , t , 0x3f3f3f3f);
    }
    return flow;
}
int S,T,tot,f[maxn],d[maxn],F,D,c1[maxn],c2[maxn];
int main() {
    freopen("usaco_open07_dining.in","r",stdin);
    freopen("usaco_open07_dining.out","w",stdout);
    scanf("%d%d%d",&n,&F,&D);
    memset(head , -1 , sizeof(head));
    S = ++ tot;
    T = ++ tot;
    for(int i = 1;i <= F;++ i)f[i] = ++ tot,AddEdge(S , f[i]);
    for(int i = 1;i <= D;++ i)d[i] = ++ tot,AddEdge(d[i] , T);
    for(int i = 1;i <= n;++ i)c1[i] = ++ tot,c2[i] = ++ tot,AddEdge(c1[i] , c2[i]);
    for(int i = 1;i <= n;++ i) {
        int x,y,z;
        scanf("%d%d",&x,&y);
        for(int j = 1;j <= x;++ j) {
            scanf("%d",&z);
            AddEdge(f[z] , c1[i]);
        }
        for(int j = 1;j <= y;++ j) {
            scanf("%d",&z);
            AddEdge(c2[i] , d[z]);
        }
    }
    printf("%d\n",Dinic(S , T));
    fclose(stdin);
    fclose(stdout);
    return 0;
}

题目要求最大，观察数据范围，结合经验，考虑贪心。

当我们现在的烤鸡翅数量大于需求时，直接卖出。

否则，寻找前面已经卖出的最大的数量，如果该数大于当前需求，则用当前数目替代该数。

正确性不难证明：根据这个方法，我们遍历到第 $i$ 个人时，已经保证在不影响卖出人数的情况下让卖出的鸡翅数量最少。

再往后遍历时，也仍然可以保证。

这样，就实现了局部最优解向整体最优解的转变。

这个过程可以用大根堆实现。

前置芝士：CDQ分治（当然不会也无所谓，我会尽量讲明白的ヾ(◍°∇°◍)ﾉﾞ）

看别人代码都是花里胡哨的线段树，树状数组，还有丧心病狂的平衡树。

好像没几个用 CDQ分治 写的

这道题本质上就是 CDQ分治（或者说二维偏序） 的模板题

将题目最开始的输入 $a_i$ 看做是对第 $i$ 个位置上增加了 $a_i$

查询操作根据前缀和，将询问拆成 $s-1,t$ 两个查询操作

第一个记录为-，第二个为+

题目中有两个维度：时间T 和 位置x

对于两个操作：修改操作 $i$,查询操作 $j$,当且仅当 $T_i \le T_j$ 并且 $x_i \le x_j$ 时，$i$ 对 $j$有影响

（之前这个地方有疑惑，现在大概明白了，这样是正确的，感谢赵老师解答）

时间T 已经默认排好序了，就剩 位置x 需要处理一下了，并且要求处理的过程中不能破坏 时间T 的顺序性

CDQ分治 闪亮登场

它的操作主要由本篇代码中的 solve 函数完成

solve(l,r) 分为三步：

solve(l,mid)  solve(mid+1,r) 以及处理 $[l,mid]$ 对 $[mid+1,r]$ 的影响

要注意的是，这里的处理必须比较容易进行（比如加法，减法，取min，取max等）

这个算法的正确性在蓝书上和网上都有证明，此处略。

对我而言，CDQ分治 最难的其实是理解

以这个题目为例，我们要计算的是满足 $T_i \le T_j$ 并且 $x_i \le x_j$ 的二元组 (i,j) 产生的影响。

正如上面所言，时间T 不能被打乱，还要计算 $x_i \le x_j$

而 CDQ分治 处理这个问题的方法，大多可以在证明中理解。

$\forall k \in [mid+1,r]$，$[mid+1,k-1]$ 这一段产生的影响已经在递归中计算过了。

主要看的就是 $[l,mid]$ 这一段。

可以发现，不管 $[l,mid]$ 这一段怎样交换，改变，这里面的元素在现在的 solve(l,r) 中始终处于 $[l,mid]$ 这一段。

而这意味着什么呢？

也许 $[l,mid]$ 这一段的内部 时间T 是混乱的，但是并不影响这一段中任何一个操作对 $[mid+1,r]$ 的影响！！！

那么，我们可以在 solve 函数结束，各种乱七八糟的影响计算完毕后，把 $[l,r]$ 中的操作序列调整成我们想要的样子。

比如在这个题目里，solve 函数中，我们按照归并排序的方式，将 $[l,mid]$ 和 $[mid+1,r]$ 以 $x$ 为关键字排序

（这里有点像归并排序求逆序对，结合代码理解，或者先去看看这道题）

然后就不难理解了叭(*^▽^*)

//CDQ分治第一弹[
//STO CDQ 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn = 5e5 + 5;
struct query {
	int op,id,x,y;//id:若当前操作为询问，则为询问的编号
	//op:1为修改，2为负查询，3为正查询
	//x,y:操作的点和要增加的量 
	query() {
		op = id = x = y = 0;
	}
	query(int op,int id,int x,int y):op(op),id(id),x(x),y(y){}
}Q[maxn],b[maxn];//b数组：辅助进行归并排序 
int n,m,cnt,tot,ans[maxn];
int read() {
	int s = 0,f = 1;
	char c = getchar();
	for(;!isdigit(c);c = getchar()) {
		if(c == '-')f = -1;
	}
	for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
	return s * f;
}
void write(int x) {
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
	return ;
}
void print(int x) {
	write(x);
	putchar('\n');
	return ;
}//快读快写 
//个人对于CDQ分治的理解：
//主要是解决偏序问题，当然这些偏序不都是裸的类似逆序对这样的
//对于答案的修改可能更加繁琐一点
//但是核心思想都是用CDQ分治解决偏序
//1：solve(l,mid)，2：solve(mid+1,r)和3：(l,mid)对(mid+1,r)的影响这三块
//需要根据题目的要求自行决定顺序
//不恰当的栗子：DP
//DP时后半部分的计算直接由前半部分的影响决定
//这时就要1,3,2这样处理
//而对于本题，处理需要两个区间都有序，所以要先递归 ，即1,2,3 
void solve(int l,int r) {
	if(l >= r)return ;
	int mid = l + r >> 1;
	solve(l , mid);
	solve(mid + 1 , r);
	//此处先递归是因为CDQ分治解决偏序类似归并排序
	//需要两个区间都是有序的才能进行进一步的处理
	int i = l,j = mid + 1,sum = 0;//Mergesort part
	//sum用来统计[l,mid]的修改对[mid + 1,r]的影响 
	for(int k = l;k <= r;++ k) {
		if(j > r||(i <= mid&&Q[i].x <= Q[j].x)) {
			//此时当前的i对于[j,r]区间都有影响
			//记录在sum里，当查找到一个i，使得i无法对于j产生影响
			//那么再统计前面所有的i对当前j的影响
			//写的不太明白，可以结合下面else部分中的代码理解 
			if(Q[i].op == 1) {
				sum += Q[i].y;
			}
			b[k] = Q[i ++];
		}
		else {
			if(Q[j].op == 2) {
				ans[Q[j].id] -= sum;
			}
			else ans[Q[j].id] += sum;
			//若当前询问是-操作，那么ans[Q[j].id]减去sum值（也就是前半部分的影响）
			//若为+操作，则刚好相反 
			b[k] = Q[j ++];
		}
	} 
	for(int k = l;k <= r;++ k) {
		Q[k] = b[k];//归并排序的合并部分
		//为了保证当前递归的上一层可以快速进行，需要让Q[l~r]有序
		//结合函数开头理解 
	}
	return ;
}
int main() {
	freopen("shulie.in","r",stdin);
	freopen("shulie.out","w",stdout);
	n = read();
	for(int i = 1;i <= n;++ i) {
		int x = read();
		Q[++ cnt] = query(1 , 0 , i , x);
	}
	m = read();
	for(int i = 1;i <= m;++ i) {
		char c[10];
		scanf("%s",c + 1);
		int x = read(),y = read();
		if(c[1] == 'A') {
			Q[++ cnt] = query(1 , 0 , x , y);
		}
		else {
			Q[++ cnt] = query(2 , ++ tot , x - 1 , 0);
			Q[++ cnt] = query(3 , tot , y , 0);
		}
	}
	solve(1 , cnt);
	for(int i = 1;i <= tot;++ i)print(ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}