当前位置:网站首页>(lightoj - 1369) answering queries (thinking)
(lightoj - 1369) answering queries (thinking)
2022-07-06 16:25:00 【AC__ dream】
Topic link :Answering Queries - LightOJ 1369 - Virtual Judge
The question : Definition f(A,n) yes Result , We have two operations , One is to query the current results , The other is to put A Modify the value of an element in the array
analysis : We first find the result of the original array , Note that you cannot solve the result of the original array directly , This will time out , We can only observe the characteristics of each number to find the law to solve , such as a[i] Will act as n-i Secondary addend , And as a i-1 Times subtraction , So in general a[i] Will be added (n-2*i+1) Time , Using this law, we can o(n) Calculate the result of the original array , Let's analyze it a little bit What will be the impact of modifying an element on the result , For example a[x] yes m, Now change it to n, So for any containing a[x] The value of the expression of will change accordingly ,a[x] There are two ways in expressions , One is a[i]-a[x](i<x), The other is a[x]-a[j](j>x), The value of the former expression will increase m-n Yes x-1 This happens to expressions , The latter expression will reduce m-n, Yes n-x This happens to expressions , Generally speaking, there is an increase (2*x-n-1) individual (m-n), So we can o(1) The result was modified , Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
signed main()
{
int T;
cin>>T;
for(int _=1;_<=T;_++)
{
printf("Case %lld:\n",_);
long long ans=0;
int n,q;
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
ans+=(n-2*i+1)*a[i];
while(q--)
{
int op,x,y;
scanf("%lld",&op);
if(op==1) printf("%lld\n",ans);
else
{
scanf("%lld%lld",&x,&y);
x++;
ans+=(a[x]-y)*(2*x-1-n);
a[x]=y;
}
}
}
return 0;
}
边栏推荐
- Problem - 1646C. Factorials and Powers of Two - Codeforces
- Useeffect, triggered when function components are mounted and unloaded
- Acwing - game 55 of the week
- Interesting drink
- QT实现窗口渐变消失QPropertyAnimation+进度条
- (lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
- Discussion on QWidget code setting style sheet
- Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
- What is the difficulty of programming?
- window11 conda安装pytorch过程中遇到的一些问题
猜你喜欢
Codeforces round 797 (Div. 3) no f
读取和保存zarr文件
Advancedinstaller安装包自定义操作打开文件
1689. Ten - the minimum number of binary numbers
2027. Minimum number of operations to convert strings
Codeforces Round #801 (Div. 2)A~C
Local visualization tools are connected to redis of Alibaba cloud CentOS server
OneForAll安装使用
<li>圆点样式 list-style-type
Raspberry pie 4b64 bit system installation miniconda (it took a few days to finally solve it)
随机推荐
Candy delivery (Mathematics)
Problem - 1646C. Factorials and Powers of Two - Codeforces
<li>圆点样式 list-style-type
Codeforces Round #802(Div. 2)A~D
Alice and Bob (2021 Niuke summer multi school training camp 1)
< li> dot style list style type
Share an example of running dash application in raspberry pie.
Oneforall installation and use
Codeforces - 1526C1&&C2 - Potions
AcWing:第56场周赛
Opencv learning log 24 -- Hough transform 2 (maximum interval and minimum length can be limited)
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
第 300 场周赛 - 力扣(LeetCode)
1323. Maximum number of 6 and 9
Acwing - game 55 of the week
969. Pancake sorting
input 只能输入数字,限定输入
Anaconda下安装Jupyter notebook
875. 爱吃香蕉的珂珂 - 力扣(LeetCode)
Educational Codeforces Round 130 (Rated for Div. 2)A~C