Merchant
考场思路：
考场上想到了二分，但是并不知道nth_element这种高端的东西，于是用了优先队列。但是由于忘记了清空队列，所以挂了。
正解：
由题意可知，每一个物品的集合必定是一个一次函数。随着时间的增加，最大值是先降后增的。在下降区段，必定是没有零点优的，所以只需要先特判零点，然后对于以后的时间进行二分,使用nth_element,O(N)求出最小的n-m个值，选出剩下的至多m个值，判断是否符合条件，变更l，r。
tip：nth_element(a+1,a+m+1,a+n+1);能够在O(n)时间内处理出最小的m个值（是无序的）。
#include<bits/stdc++.h>
#define lt long long
#define int long long
using namespace std;
const int N=10000050;
int n,m;
lt s;
lt k[N],b[N],a[N];
lt ans,ens;
signed main(){
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=n;++i){
scanf("%lld%lld",&k[i],&b[i]);
a[i]=b[i];
}
sort(a+1,a+1+n);
for(int i=n;i>=n-m+1;i--){
ans+=a[i];
if(ans>=s){
printf("0\n");
return 0;
}
}
lt l=0,r=10000000005;
while(1<r-l){
lt mid=(r+l)>>1;
for(int i=1;i<=n;++i){
a[i]=k[i]*mid+b[i];
}
nth_element(a+1,a+n-m+1,a+n+1);
bool b=0;
ans=0;
for(int i=n;i>=n-m+1;--i){
if(a[i]>0)ans+=a[i];
if(ans>=s){
b=1;
break;
}
}
if(b){
r=mid;
}
else{
l=mid;
}
// printf("%lld %lld %lld\n",mid,ans,s);
}
cout<<r<<endl;
return 0;
}
Equation
考场思路：
考场上想到了正解，然鹅由于失智行为，只得了3分(不删freopen都能得这么多分)
正解：
从根节点向下按照式子推，可以发现，每一个数都可以表示成 \(x_{i} =k+x_{1}\) 或 \(x_{i} =k-x_{1}\) 的形式，此时对于询问我们便可以轻松的回答询问了。对于修改操作我们发现，深度奇偶性相同的两个点，修改其中一个点，对于另一个的贡献是相同的；而对于相反的点，修改其中一个点，对于另一个的贡献是相反的。知道了这一点我们就可以建出线段树（用树状数组更快，线段树要大力卡常）去维护修改值，询问时对于奇数点与偶数点分别处理就好了。
#include<bits/stdc++.h>
#define lt long long
using namespace std;
const int N=1000050;
int n,q;
int head[N],tot;
int dep[N],fa[N],id[N],rk[N],idnt,size[N];
lt t[N*4],val[N],yb[N];
struct edge{
int nxt,to,dis;
}e[N*2];
inline int rd(){
int x=0,f=1;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘){
if(ch==‘-‘)
f=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void ade(int x,int y,int z){
e[++tot].nxt=head[x];
e[tot].to=y;
e[tot].dis=z;
head[x]=tot;
}
void dfs1(int u){
id[u]=++idnt;
rk[idnt]=u;
size[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dep[v]=dep[u]+1;
val[v]=e[i].dis-val[u];
dfs1(v);
size[u]+=size[v];
}
}
inline void pushdown(int u){
if(!t[u]) return;
t[u<<1]+=t[u];
t[u<<1|1]+=t[u];
t[u]=0;
}
void edit(int u,int l,int r,int ll,int rr,lt x){
if(l>rr||r<ll){
return;
}
if(l>=ll&&r<=rr){
t[u]+=x;
return;
}
pushdown(u);
register int mid=(l+r)>>1;
edit(u<<1,l,mid,ll,rr,x);
edit(u<<1|1,mid+1,r,ll,rr,x);
}
int ask(int u,int l,int r,int x){
if(l==r){
return t[u];
}
pushdown(u);
register int mid=(l+r)>>1,ans;
if(x<=mid){
ans=ask(u<<1,l,mid,x);
}
else{
ans=ask(u<<1|1,mid+1,r,x);
}
return ans;
}
void que(int x,int y,lt z){
if((dep[x]&1)==(dep[y]&1)){
if(!(dep[x]&1)){
lt anx,any,cnx,cny,cx;
anx=ask(1,1,n,id[x]);
any=ask(1,1,n,id[y]);
cnx=anx+val[x];
cny=any+val[y];
cx=cnx+cny-z;
if(cx&1){
printf("none\n");
return;
}
else{
cx/=2;
printf("%lld\n",cx);
}
}
else{
lt cnx,cny,cx;
cnx=ask(1,1,n,id[x]);
cny=ask(1,1,n,id[y]);
cnx=val[x]-cnx;
cny=val[y]-cny;
cx=z-cnx-cny;
if(cx&1){
printf("none\n");
return;
}
else{
cx/=2;
printf("%lld\n",cx);
}
}
}
else{
if(dep[x]&1){
lt cnx,cny;
cnx=ask(1,1,n,id[x]);
cny=ask(1,1,n,id[y]);
cnx=val[x]-cnx;
cny+=val[y];
if(cnx+cny==z){
printf("inf\n");
}
else{
printf("none\n");
}
}
else{
swap(x,y);
lt cnx,cny;
cnx=ask(1,1,n,id[x]);
cny=ask(1,1,n,id[y]);
cnx=val[x]-cnx;
cny+=val[y];
// printf("%d %d %d %d %d %d",x,y,anx,cnx,any,cny);
if(cnx+cny==z){
printf("inf\n");
}
else{
printf("none\n");
}
}
}
}
int main(){
// freopen("shuju.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%d%d",&n,&q);
int fc,wc;
for(register int i=2;i<=n;i++){
fc=rd(),wc=rd();
fa[i]=fc;
yb[i]=wc;
ade(fc,i,wc);
}
dep[1]=1;
dfs1(1);
int tp,uc,vc;
lt sc,we;
for(register int i=1;i<=q;++i){
tp=rd();
if(tp==1){
uc=rd(),vc=rd(),sc=rd();
que(uc,vc,sc);
}
else{
uc=rd(),we=rd();
if(!(dep[uc]&1)){
edit(1,1,n,id[uc],id[uc]+size[uc]-1,we-yb[uc]);
yb[uc]=we;
}
else{
edit(1,1,n,id[uc],id[uc]+size[uc]-1,yb[uc]-we);
yb[uc]=we;
}
}
}
return 0;
}
正解：
很是难写的一道题。
首先枚举矩形的右边界，对于每一个有边界，从右往左枚举左边界
考虑左右边界在A，B之间的矩形，都可以以A到B为长，对于在蓝色区间的C点，和在橙色区间的D点，若两者和A，B构成点集，则上边界为C点，下边界为D点，左边界为B，右边界为A。每这样的两对点都能对答案产生贡献，于是得出以下式子
\(\displaystyle\sum_{i=1}^{mn}\displaystyle\sum_{j=mx}^{inf}(j-i)\)
将i从里面提出来，定义size[A]为从零到A的节点数量，定义sum[A]为从零到A的节点的纵坐标总和。
每一个C节点都有size[A]个贡献,减去的D节点的和为sum[A]
\(\displaystyle\sum_{i=mx}^{inf}i*size[A]-sum[A]\)
再将i表示出来
\(sum[i]*size[j]-sum[j]*size[i]\)
如果再l与r上有多个点时
对于绿色部分显然不能用B和A时维护，否则会有重复，所以在B和A时，只能维护蓝色区间，要在C和A时，再去维护黄色区间。
对于sum和size使用树状数组维护与查询（每次移动右边界时，清空树状数组）
#include<bits/stdc++.h>
#define lt long long
using namespace std;
const int N=10050,mod=1e9+7;
int n;
int x[N],y[N];
vector<int> mc[3000];
int xmx,ymx;
int size[3000],sum[3000];
bool vis[3000][3000];
lt ens,anx,any;
int low(int x){
return x&-x;
}
void add(int x,int y){
x++;
for(int i=x;i<=ymx+1;i+=low(i)){
size[i]+=1;
sum[i]+=y;
}
}
void ask(int x,int y){
y++;
lt ana=0,anb=0,bna=0,bnb=0;
for(int i=x;i;i-=low(i)){
ana+=size[i];
anb+=sum[i];
}
for(int i=y;i;i-=low(i)){
bna+=size[i];
bnb+=sum[i];
}
// printf("[%d %d %d %d]\n",ana,anb,bna,bnb);
anx=bna-ana;any=bnb-anb;
// if(anx<0) anx=0;
// if(any<0) any=0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&x[i],&y[i]);
xmx=max(xmx,x[i]);
ymx=max(ymx,y[i]);
mc[x[i]].push_back(y[i]);
}
for(int i=1;i<=xmx;++i){
sort(mc[i].begin(),mc[i].end());
mc[i].push_back(ymx+1);
}
for(int i=1;i<=xmx;++i){
// cout<<endl<<i<<" rk "<<ens<<endl;
memset(size,0,sizeof(size));
memset(sum,0,sizeof(sum));
int szi=mc[i].size()-1;
if(!szi)continue;
for(int k=0;k<szi;++k){
if(!vis[i][mc[i][k]]){
vis[i][mc[i][k]]=1;
add(mc[i][k],mc[i][k]);
}
}
for(int j=i-1;j>=1;--j){
int szj=mc[j].size()-1;
if(!szj) continue;
for(int k=0;k<szj;++k){
if(!vis[i][mc[j][k]]){
vis[i][mc[j][k]]=1;
add(mc[j][k],mc[j][k]);
}
}
int tp1=0,tp2=0,up=max(mc[i][0],mc[j][0]);
while(mc[i][tp1+1]<=up) tp1++;
while(mc[j][tp2+1]<=up) tp2++;
while(tp1<szi&&tp2<szj){
int uup=min(mc[i][tp1+1],mc[j][tp2+1]);
int down=min(mc[i][tp1],mc[j][tp2]);
int aa,bb,cc,dd;
ask(up,uup-1);
aa=anx,bb=any;
ask(1,down);
cc=anx,dd=any;
ens=(ens+((lt)(i-j)*(bb*cc-dd*aa)))%mod;
up=uup;
if(mc[i][tp1+1]<=up)tp1++;
if(mc[j][tp2+1]<=up)tp2++;
// printf("%d %d|",tp1,tp2);
}
}
}
printf("%lld\n",ens);
return 0;
}