3.5 美团 区间问题 100%
题目就是给n个数字，m个操作，可以区间add，也可以区间query求和
问这n个数字怎么排出来，可以使得sum{query} 最大
解法：
题目前一半就是线段树模板题，处理区间的增长和求和
后一段才是精华，需要知道怎么排才能使得和最大
要使得和最大，那么某个位置的被查询次数越多，说明这个位置的数的贡献值越大。于是得出最大的数应该放在查询次数最多的那个位置上
所以就是先算每个位置被算了几次，对整个位置的次数进行从小到大排序，依次把原数据也从小到大放进去。然后套线段树即可
代码：（变量有点丑，轻喷）
#include <iostream>
#include <queue>
#include <stdio.h>
#include "map"
#include "string"
#include "string.h"
#include "stack"
#include<algorithm>
using namespace std;
#define MAX 5002
#define LL long long
int tree[4*MAX];
int lz[4*MAX];
int a[MAX]; //原数组
int l[MAX];
int r[MAX];
int x[MAX]; //操作标志，1表示求和，2表示增长
int z[MAX]; // 2的时候的加数
int last[MAX];
struct Node{
int data;
int index;
} origin[MAX]; //位置数据，最开始data都是0，index就是位置
bool compare(Node a,Node b)
{
return a.data <b.data ; //对data排序
} //< 升序 >降序
void init(){
memset(tree,0,sizeof(tree));
}
void push_down(int node,int l,int r){
if(lz[node]){
int mid = (l+r) / 2;
lz[node*2] += lz[node];
lz[node*2 + 1] += lz[node];
// 注意线段树的数据更新方式要一致
tree[node*2] += 1LL*(mid - l + 1)*lz[node];
tree[node*2 + 1] += 1LL*(r - mid)*lz[node];
lz[node] = 0;
}
}
// 区间查找
LL query_range(int node,int L,int R,int l,int r){
if(l <= L && r >= R) return tree[node];
push_down(node,L,R);
int mid = (L+R) / 2;
LL sum = 0;
if(mid >= l) sum += query_range(node*2,L,mid,l,r);
if(mid < r) sum += query_range(node*2 + 1,mid+1,R,l,r);
return sum;
}
void update_range(int node,int l,int r,int L,int R,int add){
if(l <= L && r >= R){
lz[node] += 1LL*add;
tree[node] += 1LL*(R - L + 1)*add; // 更新方式
return;
}
push_down(node,L,R);
int mid = (L+R) / 2;
if(mid >= l) update_range(node*2,l,r,L,mid,add);
if(mid < r) update_range(node*2 + 1,l,r,mid+1,R,add);
tree[node] = tree[node*2] + tree[node*2 + 1];
}
void build(int node,int l,int r) {
if (l == r) { // 到达叶子节点，赋值
tree[node] = last[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid); // 进入子树开始递归
build(node * 2 + 1, mid + 1, r);
tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 回溯
}
int main() {
int n, m;
cin >> n >> m;
init();
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i =1;i<=n;i++){
origin[i].data = 0;
origin[i].index = i;
}
//build(1, 1, n);
for(int i=0;i<m;i++){
cin >> x[i] >> l[i] >> r[i];
if(x[i] == 1){
for(int j=l[i]; j<=r[i]; j++){
origin[j].data = origin[j].data+1;
}
} else {
cin >> z[i];
}
}
sort(a+1, a+n+1);
sort(origin+1, origin+n+1, compare);
for(int i=1;i<=n;i++){
//cout << a[i] <<endl;
//cout << origin[i].data << " " << origin[i].index << endl;
//cout << origin[i].index << endl;
last[origin[i].index] = a[i];
}
//cout << endl;
build(1, 1, n);
LL ans = 0;
for(int i=0;i<m;i++){
if(x[i] == 1){
long long sum = query_range(1, 1, n, l[i], r[i]);
ans = ans + sum;
//cout << sum << endl;
} else {
update_range(1, l[i], r[i], 1, n, z[i]);
}
}
cout << ans <<endl;
return 0;
}
