USACO23OPEN-Silver A

题目来源

洛谷：USACO23OPEN-Silver Milk Sum(A)

SPOJ：USACO23OPEN-Silver Milk Sum(A)

题解： USACO23OPEN-Silver Milk Sum(A)

题面简述

给定数组，在数组中依次选出一个元素构成排列。

定义。

现在给出个操作，每个操作有两个数和表示将替换成，对于每一个操作求出操作后的的最大值，每次操作后数组还原成原样。

题目描述

农民约翰的头奶牛的产奶量为整数。也就是说，第头奶牛每分钟产奶单位。

每天早上，农场主约翰开始把牲口棚里的头牛都拴在挤奶机上。他被要求一个接一个地解开它们，把它们送出去进行日常锻炼。他送出去的第一头奶牛在挤奶一分钟后就会解开钩，送出去的第二头奶牛在挤奶一分钟后就会解开钩，以此类推。因为第一头奶牛（例如奶牛）在挤奶机上只花了分钟，所以她只贡献了单位的总牛奶。第二头奶牛（比如奶牛）在挤奶机上总共花了分钟，因此贡献了单位的总牛奶。第三头奶牛（比如奶牛）贡献了个单位，以此类推。假设代表农场主约翰按最优顺序解开奶牛，他总共能收集到的最大牛奶量。

农场主约翰很好奇，如果他的奶牛群的牛奶产量有所不同，会受到什么影响。对于每个查询，每个查询由两个整数和指定，请计算如果设置为，的新值将是什么。注意，每个查询都考虑一个临时的潜在变化，独立于所有其他查询；也就是说，在考虑下一个查询之前恢复到其原始值。

输入格式

第一行输入一个整数。

第二行输入个整数。

第三行输入一个整数。

接下来有行，每行两个整数和。

输出格式

输出共有行，每行一个整数，依次表示第次查询的所对应的值。

题解

言简意赅，该题有几个性质：

将数组按从小到大顺序排列， ;
对于每次操作，可以用求得修改值在数组中的位置；
考虑每次修改对的影响 ，分种情况讨论，设表示修改的位置对应的在数组的位置，设表示修改的值在数组中的位置，分,,三种情况枚举即可。

代码

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 151234;
int sum[N],ans;
int n,q,a[N],b[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    cin>>n;For(i,1,n) a[i]=b[i]=input();
    sort(b+1,b+n+1);
    For(i,1,n) sum[i]=sum[i-1]+b[i],ans+=i*b[i];
    cin>>q;
    while(q--){
        int k=input(),w=input(),res=0;
        int x=lower_bound(b+1,b+n+1,a[k])-b;
        int y=lower_bound(b+1,b+n+1,w)-b;
        if(x==y) res=ans-b[x]*x+w*y;else
        if(x>y) res=ans+sum[x-1]-sum[y-1]-b[x]*x+w*y;
        else res=ans-(sum[y-1]-sum[x])-b[x]*x+w*(y-1);
        cout<<res<<'\n';
    }
    return 0;
}