当前位置:网站首页>(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;
}
边栏推荐
- (lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
- Li Kou - 298th weekly match
- OneForAll安装使用
- input 只能输入数字,限定输入
- It is forbidden to trigger onchange in antd upload beforeupload
- Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
- MariaDB的安装与配置
- 969. Pancake sorting
- 1903. Maximum odd number in string
- Opencv learning log 28 -- detect the red cup cover
猜你喜欢
Vs2019 initial use
力扣——第298场周赛
QT按钮点击切换QLineEdit焦点(含代码)
Sword finger offer II 019 Delete at most one character to get a palindrome
window11 conda安装pytorch过程中遇到的一些问题
7-1 understand everything (20 points)
去掉input聚焦时的边框
Codeforces Round #799 (Div. 4)A~H
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
1005. Maximized array sum after K negations
随机推荐
875. Leetcode, a banana lover
Codeforces Round #802(Div. 2)A~D
Summary of FTP function implemented by qnetworkaccessmanager
树莓派4B安装opencv3.4.0
It is forbidden to trigger onchange in antd upload beforeupload
(POJ - 1458) common subsequence (longest common subsequence)
Alice and Bob (2021 Niuke summer multi school training camp 1)
useEffect,函數組件掛載和卸載時觸發
Flask框架配置loguru日志库
Click QT button to switch qlineedit focus (including code)
Opencv learning log 29 -- gamma correction
Codeforces Round #798 (Div. 2)A~D
QT implementation window gradually disappears qpropertyanimation+ progress bar
Is the sanic asynchronous framework really so strong? Find truth in practice
QT implementation fillet window
window11 conda安装pytorch过程中遇到的一些问题
图图的学习笔记-进程
Problem - 922D、Robot Vacuum Cleaner - Codeforces
栈的经典应用—括号匹配问题
Li Kou - 298th weekly match