170

#include<iostream>
using namespace std;

constexpr int N = 100010;
int n,m;
int dd[N];
int pre[N];

void insert(int l, int r, int v){
//差分 l 位置+v  r+1 位置-v
dd[l] += v;
dd[r+1] -= v;
}

int main(){
cin >> n >> m;

for(int i = 1; i <= n; ++i){
int num;
cin >> num;
insert(i, i, num);
}

for(int i = 1; i <= m; ++i){
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}

for(int i = 1; i <= n; ++i){
pre[i] = pre[i-1] + dd[i];
cout << pre[i] << " ";
}
}


#include<iostream>
using namespace std;

int n, m, q;
constexpr int N = 1010;
int dd[N][N];
int pre[N][N];

void insert(int x1, int y1, int x2, int y2, int v){
dd[x1][y1] += v;
dd[x2+1][y2+1] +=v;
dd[x2+1][y1] -= v;
dd[x1][y2+1] -= v;
}

int main(){

cin >> n >> m >> q;

for (int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
int v;
cin >> v;
insert(i,j,i,j,v);
}
}

for (int i = 1;i <= q; ++i){
int x1, y1, x2, y2, v;
cin >> x1 >> y1 >> x2 >> y2 >> v;
insert(x1,y1,x2,y2,v);
}

for (int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + dd[i][j];
cout << pre[i][j] <<' ';
}
cout << endl;
}
}


#include<iostream>
using namespace std;

constexpr int N = 100010;
int n,m;
int dd[N];
int pre[N];

void insert(int l, int r, int v){
//差分 l 位置+v  r+1 位置-v
dd[l] += v;
dd[r+1] -= v;
}

int main(){
cin >> n >> m;

for(int i = 1; i <= n; ++i){
int num;
cin >> num;
insert(i, i, num);
}

for(int i = 1; i <= m; ++i){
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}

for(int i = 1; i <= n; ++i){
pre[i] = pre[i-1] + dd[i];
cout << pre[i] << " ";
}
}


#include<iostream>
using namespace std;

constexpr int N = 1010;
int n, m, q;
int pre[N][N];

int main(){
cin >> n >> m >> q;

for(int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
int num = 0;
cin >> num;
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + num;
}
}

for(int i = 0; i < q; ++i){
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >>y2;
cout << pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1 - 1][y1 -1] << endl;
}

}


#include<iostream>
using namespace std;

int n,m;
constexpr int N = 100010;
int nums[N];
int prefix[N];

int main(){
cin >> n >> m;
int num = 0;
for (int i = 1;i <= n; ++i){
cin >> num;
prefix[i] = prefix[i-1] + num;
}

for(int i = 1;i <= m; ++i){
int l = 0;
int r = 0;
cin >> l >> r;
cout << prefix[r] - prefix[l-1] << endl;
}
}


#include<iostream>
using namespace std;
double n;
constexpr double erp = 1e-8;
int main(){
cin >> n;

double l = -10000;
double r = 10000;

while(r - l > erp){
double mid = (l + r)/2 ;
if(mid * mid * mid >= n) r = mid;
else l = mid;
}

printf("%.6f",l) ;

}


#include<iostream>
using namespace std;

constexpr int  N = 100010;
int n, q;
int nums[N];

void search1(int q){
int l = 0;
int r = n - 1;

while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= q) r = mid;
else l = mid + 1;
}

if(nums[l] != q) cout<< "-1" << " " << "-1" << endl;
else {
cout << l << " ";
int l = 0;
int r = n - 1;

while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] <= q) l = mid;
else r = mid - 1;
}

cout<< l << endl;
}

}

int main(){
cin >> n >> q;
for (int i = 0; i < n; ++i){
cin >> nums[i];
}

for(int i = 0; i < q; ++i){
int q = 0;
cin >>  q;
search1(q);
}
}


#include<iostream>

using namespace std;

constexpr int N = 100010;
int n;
int nums[N];
long long res;

void reverse_num(int s, int e){
if(s >= e) return;
int mid = (s + e) >> 1;
reverse_num(s, mid);
reverse_num(mid + 1, e);

//合并
int i = s;
int j = mid + 1;
int cur = 0;
int tmp[e - s + 1];

while(i <= mid && j <= e){
if(nums[i] <= nums[j]) tmp[cur++] = nums[i++];
else{
tmp[cur++] = nums[j++];
res += mid - i + 1;
}
}
while(i <= mid) tmp[cur++] = nums[i++];
while(j <= e) tmp[cur++] = nums[j++];

for(int ii = s; ii <= e; ++ii){
nums[ii] = tmp[ii - s];
}
}

int main(){
scanf("%d",&n);

for(int i = 0; i< n; ++i){
scanf("%d", &nums[i]);
}
reverse_num(0, n - 1);
printf("%lld", res);

}


#include<iostream>

constexpr int N = 100010;
int n;
int nums[N];

void merge_sort(int s, int e){
if(s >= e) return;
int mid = (s + e) >> 1;
merge_sort(s, mid);
merge_sort(mid+1 , e);

//合并
int tmp[e-s+1];

int i = s;
int j = mid + 1;
int cur = 0;
while(i <= mid && j<= e){
if(nums[i]<= nums[j]) tmp[cur++] = nums[i++];
else tmp[cur++] = nums[j++];
}
while(i<=mid) tmp[cur++] = nums[i++];
while(j<=e) tmp[cur++] = nums[j++];

for (int ii = s; ii <= e; ++ii){
nums[ii] = tmp[ii - s];
}
}

int main(){
scanf("%d",&n);
for(int i = 0; i < n; ++i){
scanf("%d", &nums[i]);
}
merge_sort(0,n-1);
for(int i = 0; i< n; ++ i){
printf("%d ", nums[i]);
}
}


#include<iostream>
#include<vector>
using namespace std;

int n,k;

int quickchoose(vector<int>& nums, int s, int e ,int  k){
if(s >= e) return nums[s];
int l = s - 1;
int r = e + 1;
int p = nums[(l + r) >> 1];
while(l<r){
do(++l);while(nums[l] < p);
do(--r);while(nums[r] > p);
if(r > l) swap(nums[l], nums[r]);
}
int sl = r - s + 1;
if(k <= sl ) return quickchoose(nums, s, r, k);
return  quickchoose(nums, r+1, e, k - sl);
}

int main(){
scanf("%d%d", &n, &k);
vector<int> nums(n);
for(int i = 0; i < n; ++ i){
scanf("%d", &nums[i]);
// printf("%d", nums[i]);
}
printf("%d",quickchoose(nums, 0 , n - 1, k));
}