当前位置:网站首页>AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
2022-07-06 03:51:00 【Jacob* ̄▽ ̄*】
The question :
This problem requires the use of tree array Interval modification and Interval query .
Ideas :
stay Last question in , We maintain an original array with a tree array a The differential array of b, For every instruction “C l r d
”, hold b[i]
add d
, And then b[r+1]
subtract d
.
What has been discussed is :b
Of 1~x
The prefix and b[1~x]
After these instructions ,a[x]
Increased value .
that a
The prefix and of the sequence a[1~x]
The overall value added is
The above formula can be further rewritten into :
Derivation process :
Therefore, in this problem, we can consider adding a tree array , For maintenance i*b[i]
And , The above formula can be calculated directly .
To be specific , We build two tree arrays , Respectively c1
, c2
, Initially, all values are 0
, For every instruction “C l r d
”, Perform four operations :
- ①
c1
Ofl
Position plusd
. - ②
c1
Ofr+1
Position subtractiond
. - ③
c2
Ofl
Position plusl*d
. - ④
c2
Ofr+1
Position subtraction(r+1)*d
.
For every instruction “Q l r
”, We can directly apply the formula derived above to calculate .
This problem brings us a kind of thought , Separate items that contain multiple variables , Make different variables in the formula independent of each other , This idea is very important .
Time complexity :
O(mlogn)
Code :
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n, m;
int a[N], c1[N], c2[N];
int read() {// Fast reading
int x=0,f=1; char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
}
inline int lowbit(int x) {return x & (-x);}
int ask(int c[], int x)
{
int ans = 0;
while(x) {ans+=c[x], x-=lowbit(x);}
return ans;
}
int add(int x, int y, int c[])
{
for(; x<=n; x+=lowbit(x)) c[x]+=y;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
a[i] = read();
add(i, a[i]-a[i-1], c1), add(i, i*(a[i]-a[i-1]), c2);
}
while(m--)
{
char op[2];
int l, r, d;
scanf("%s", op);
l = read(), r = read();
if(*op=='C')
{
d = read();
add(l, d, c1), add(l, l*d, c2);
add(r+1, -d, c1), add(r+1, -(r+1)*d, c2);
}
else
{
printf("%lld\n", (r+1)*(ask(c1, r)) - ask(c2, r) - l*(ask(c1, l-1)) + ask(c2, l-1));
}
}
return 0;
}
边栏推荐
- After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
- Ks008 SSM based press release system
- Ethernet port &arm & MOS &push-pull open drain &up and down &high and low sides &time domain and frequency domain Fourier
- Remote Sensing Image Super-resolution and Object Detection: Benchmark and State of the Art
- Pandora IOT development board learning (HAL Library) - Experiment 9 PWM output experiment (learning notes)
- 登录mysql输入密码时报错,ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: NO/YES
- Record the process of reverse task manager
- Custom event of C (31)
- [meisai] meisai thesis reference template
- Simple blog system
猜你喜欢
JVM的手术刀式剖析——一文带你窥探JVM的秘密
SWC introduction
3.1 rtthread 串口设备(V1)详解
Plus d'un milliard d'utilisateurs de grandes entreprises comme Facebook ont été compromis, il est temps de se concentrer sur le did
Exchange bottles (graph theory + thinking)
Remote Sensing Image Super-resolution and Object Detection: Benchmark and State of the Art
Alibaba testers use UI automated testing to achieve element positioning
BUAA喜鹊筑巢
WPF effect Article 191 box selection listbox
1、工程新建
随机推荐
Pytoch foundation - (1) initialization of tensors
JVM的手术刀式剖析——一文带你窥探JVM的秘密
LTE CSFB test analysis
Simple blog system
Facebook等大廠超十億用戶數據遭泄露,早該關注DID了
[rust notes] 18 macro
How do we make money in agriculture, rural areas and farmers? 100% for reference
Teach you to build your own simple BP neural network with pytoch (take iris data set as an example)
简易博客系统
P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
[American competition] mathematical terms
Blue Bridge Cup - Castle formula
2.2 STM32 GPIO操作
Schnuka: 3D vision detection application industry machine vision 3D detection
2.2 fonctionnement stm32 GPIO
Blue style mall website footer code
Proof of Stirling formula
ESP32_ FreeRTOS_ Arduino_ 1_ Create task
【FPGA教程案例12】基于vivado核的复数乘法器设计与实现
C mouse event and keyboard event of C (XXVIII)