Description
在一个教室里有 \(n\) 排座位，每排有 \(6\) 个，从左至右标号分别为 ABCDEF，其中 C 和 D 中有过道，通往教室前端和后端的两个房间，每个房间最开始没有人,每个座位上开始都有人。
有 \(m\) 个不同的学生会依次提前交卷，先从这一排走到过道上，在从过道走到前面或后面的房间里。每个提前交卷的学生有一个不满度，表示为 \(A\times x+B\times y\)，其中 \(A,B\) 是给定的常数，\(x\) 为经过的同学数量，由过道两侧的同学以及在过道与座位之间的同学组成（不包含自己）。\(y\) 为在到达房间前房间内的人数。
你需要安排这些学生是去前面还是后面的房间，求不满度之和的最小值。
Solution
画个图：
前端
ABC||DEF
ABC||DEF
ABC||DEF
后端
暴力就是 dp 求解。
本题最关键的性质就是在确定两个房间最终分别有多少人后，可以直接算出不满度中 \(B\times y\) 的部分，同时第 \(i\) 个人去前面和去后面的人数是确定的。
设前面的房间有 \(i\) 个人，后面的有 \(m-i\) 个人，那么不满度之和的后半部分就是 \(B\times(\dfrac{i\times(i-1)}{2}+\dfrac{(m-i)\times(m-i-1)}{2})\)。
求经过了多少人，就先将其分为两个部分，走到过道经过多少人就直接分讨当前座位的编号，开 \(vis_{i,j}\) 记录第 \(i\) 排第 \(j\) 个座位上还有没有人。过道上经过的人相当于一个前缀和，\(sum_i\) 表示从第 \(i\) 排走到教室前面经过的人数，如果在他之前过道上有人离开就实时更新，用树状数组维护。
注意如果他就是坐在过道上的，要先更新 \(sum\) 再算值，不然会把自己也算进去。
这样我们只需要判断一个学生是去前面还是去后面，设去前面不满度为 \(u_i\)，去后面为 \(d_i\)。
假设所有人都先去了前面，将每个学生的 \(u_i-d_i\) 从大到小排序，这样选前面 \(k\) 个去后面肯定更优，然后枚举 \(k\) 的所有情况（\(0\sim m\)），对于每种情况算出不满度之和，然后取最小即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
long long A,B;
long long tr[100010];
bool vis[100010][8];
struct node{
long long u,d;
}a[100010];
int lowbit(int x){
return x&(-x);
}
void add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
tr[i]+=val;
}
}
long long query(int x){
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)){
ans+=tr[i];
}
return ans;
}
void read(int &x,int &y){ //特殊读入方式
x=0;
string s;
cin>>s;
for(int i=0;i<s.size()-1;i++){ //得出排数
x=(x<<3)+(x<<1)+s[i]-'0';
}
y=s[s.size()-1]-'A'+1;
}
bool cmp(node x,node y){
return (x.u-x.d)>(y.u-y.d);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>A>>B;
for(int i=1;i<=n;i++){
add(i,2);
for(int j=1;j<=6;j++){
vis[i][j]=1;
}
}
long long tmp=0;
for(int i=1;i<=m;i++){
int x,y;
read(x,y);
if(y==1) tmp+=vis[x][2]; //走到过道上要经过多少人
if(y==6) tmp+=vis[x][5];
if(y==3||y==4) add(x,-1); //在过道上就更新sum
vis[x][y]=0; //记得赋为0
a[i].u+=query(x),a[i].d+=query(n)-query(x-1); //去前面和去后面，后面减的x-1是因为这一排的sum也要算
tmp+=a[i].u; //全都去前面经过的人数
}
sort(a+1,a+1+m,cmp);
long long sum=0,ans=tmp*A+m*(m-1)/2*B; //k=0时的情况
for(int i=1;i<=m;i++){
sum+=a[i].u-a[i].d; //更新经过的人数
ans=min(ans,tmp*A-sum*A+(i*(i-1)/2)*B+((m-i)*(m-i-1)/2)*B); //记得加上B*y的部分
}
cout<<ans<<endl;
return 0;
}