Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll MOD = 1000000007;
- ll dr[400000];
- ll pr[400000];
- ll sf[400000];
- ll w[400000];
- ll a[400000];
- void bl(ll v, ll l, ll r){
- if (r == l + 1){
- dr[v] = w[l];
- pr[v] = 0;
- sf[v] = 0;
- return;
- }
- bl(2 * v + 1, l, (l + r) / 2);
- bl(2 * v + 2, (l + r) / 2, r);
- dr[v] = dr[2 * v + 1] + dr[2 * v + 2];
- pr[v] = pr[2 * v + 1] + pr[2 * v + 2] + (a[r - 1] - (r - (l + r) / 2) - a[(r + l) / 2 - 1]) * dr[2 * v + 1];
- sf[v] = sf[2 * v + 1] + sf[2 * v + 2] + (a[(r + l) / 2] - a[l] - ((r + l) / 2 - l)) * dr[2 * v + 2];
- dr[v] %= MOD;
- sf[v] %= MOD;
- pr[v] %= MOD;
- }
- void ch(ll v, ll l, ll r, ll id, ll x){
- if (r == l + 1 && l == id){
- dr[v] = x;
- pr[v] = 0;
- sf[v] = 0;
- return;
- }
- if (r <= id || l > id){
- return;
- }
- ch(2 * v + 1, l, (l + r) / 2, id, x);
- ch(2 * v + 2, (l + r) / 2, r, id, x);
- dr[v] = dr[2 * v + 1] + dr[2 * v + 2];
- pr[v] = pr[2 * v + 1] + pr[2 * v + 2] + (a[r - 1] - (r - (l + r) / 2) - a[(r + l) / 2 - 1]) * dr[2 * v + 1];
- sf[v] = sf[2 * v + 1] + sf[2 * v + 2] + (a[(r + l) / 2] - a[l] - ((r + l) / 2 - l)) * dr[2 * v + 2];
- dr[v] %= MOD;
- sf[v] %= MOD;
- pr[v] %= MOD;
- }
- ll sm(ll v, ll l, ll r, ll ln, ll rn){
- if (ln >= r || rn <= l){
- return 0;
- }
- if (ln <= l && r <= rn){
- return dr[v];
- }
- return (sm(2 * v + 1, l, (l + r) / 2, ln, rn) + sm(2 * v + 2, (l + r) / 2, r, ln, rn)) % MOD;
- }
- ll prr(ll v, ll l, ll r, ll ln, ll k){
- if (ln >= r || k <= l){
- return 0;
- }
- if (ln <= l && r <= k){
- return (pr[v] + (a[k - 1] - (k - r) - a[r - 1]) * dr[v]) % MOD;
- }
- return (prr(2 * v + 1, l, (l + r) / 2, ln, k) + prr(2 * v + 2, (l + r) / 2, r, ln, k)) % MOD;
- }
- ll sff(ll v, ll l, ll r, ll k, ll rn){
- if (k >= r || rn <= l){
- return 0;
- }
- if (k <= l && r <= rn){
- return (sf[v] + (a[l] - a[k] - (l - k)) * dr[v]) % MOD;
- }
- return (sff(2 * v + 1, l, (l + r) / 2, k, rn) + sff(2 * v + 2, (l + r) / 2, r, k, rn)) % MOD;
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- ll n, q;
- cin >> n >> q;
- for (int i = 0; i < n; i++){
- cin >> a[i];
- }
- for (int i = 0; i < n; i++){
- cin >> w[i];
- }
- bl(0, 0, n);
- for (int i = 0; i < 3 * n; i++){
- cout << dr[i] << " ";
- }
- cout << endl;
- for (int i = 0; i < 3 * n; i++){
- cout << pr[i] << " ";
- }
- cout << endl;
- for (int i = 0; i < 3 * n; i++){
- cout << sf[i] << " ";
- }
- cout << endl;
- for (int i = 0; i < q; i++){
- ll x, y;
- cin >> x >> y;
- if (x < 0){
- ch(0, 0, n, -x, y);
- }
- else{
- x--;
- ll L = x, R = y;
- while (R - L > 1){
- ll mm = (R + L) / 2;
- ll t1 = sm(0,0,n,L,mm), t2 = sm(0,0,n,mm,R);
- if (t1 < t2){
- L = mm;
- }
- else{
- R = mm;
- }
- }
- cout << x << " " << L << " mememme ";
- cout << prr(0,0,n,x,L) + sff(0,0,n,L,y) << endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement