下面的第一个代码是AC,第二个代码30pts,两个代码唯一的区别就是在最后输出结果的时候第一个强制转换成了int,第二个没有。所以为什么开int过了,但是开long long过不了?
代码很丑陋,勿喷。
希望大佬解答!!
#include<bits/stdc++.h>
using namespace std;
int a[10000001],t1[10000001],t2[10000001],t[10000001];
int n,m;
int lowbit(int x){
return x&-x;
}
void init(){
for(int i=1;i<=n;i++){
t1[i]+=a[i]-a[i-1];
int j=i+lowbit(i);
if(j<=n)t1[j]+=t1[i];
}
return;
}
void exinit(){
for(int i=1;i<=n;i++){
t2[i]+=(a[i]-a[i-1])*i;
int j=i+lowbit(i);
if(j<=n)t2[j]+=t2[i];
}
return;
}
void add(int x,int k){
while(x<=n){
t[x]+=k;
x+=lowbit(x);
}
return;
}
void exadd(int x,int k){
int vk=x*k;
while(x<=n){
t1[x]+=k,t2[x]+=vk;
x+=lowbit(x);
// cout<<x<<endl;
}
return;
}
long long getsum(int x){
long long res=0;
while(x>0){
res+=t[x];
x-=lowbit(x);
}
return res;
}
long long pre_exgetsum(int x){
long long res=0,t=x;
while(x>0){
res+=t1[x]*(t+1)-t2[x];
x-=lowbit(x);
}
return res;
}
long long exgetsum(int x,int y){
return pre_exgetsum(y)-pre_exgetsum(x-1);
}
int op,x,y;
int main()
{
ios::sync_with_stdio(false);
// freopen("131_1.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
// exadd(i,a[i]-a[i-1]);
}
init();
// for(int i=1;i<=n;i++){
// cout<<t1[i]<<" ";
// }
//
// cout<<endl;
exinit();
// for(int i=1;i<=n;i++){
// cout<<t2[i]<<" ";
// }
// cout<<endl;
int tt;
while(m--){
cin>>op>>x;
if(op==1){
cin>>y>>tt;
exadd(x,tt);
exadd(y+1,-tt);
// for(int i=1;i<=n;i++){
// cout<<t1[i]<<" ";
// }
// cout<<endl;
// for(int i=1;i<=n;i++){
// cout<<t2[i]<<" ";
// }
// cout<<endl;
}
else{
cout<<(int)exgetsum(x,x)<<endl;
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a[10000001],t1[10000001],t2[10000001],t[10000001];
int n,m;
int lowbit(int x){
return x&-x;
}
void init(){
for(int i=1;i<=n;i++){
t1[i]+=a[i]-a[i-1];
int j=i+lowbit(i);
if(j<=n)t1[j]+=t1[i];
}
return;
}
void exinit(){
for(int i=1;i<=n;i++){
t2[i]+=(a[i]-a[i-1])*i;
int j=i+lowbit(i);
if(j<=n)t2[j]+=t2[i];
}
return;
}
void add(int x,int k){
while(x<=n){
t[x]+=k;
x+=lowbit(x);
}
return;
}
void exadd(int x,int k){
int vk=x*k;
while(x<=n){
t1[x]+=k,t2[x]+=vk;
x+=lowbit(x);
// cout<<x<<endl;
}
return;
}
long long getsum(int x){
long long res=0;
while(x>0){
res+=t[x];
x-=lowbit(x);
}
return res;
}
long long pre_exgetsum(int x){
long long res=0,t=x;
while(x>0){
res+=t1[x]*(t+1)-t2[x];
x-=lowbit(x);
}
return res;
}
long long exgetsum(int x,int y){
return pre_exgetsum(y)-pre_exgetsum(x-1);
}
int op,x,y;
int main()
{
ios::sync_with_stdio(false);
// freopen("131_1.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
// exadd(i,a[i]-a[i-1]);
}
init();
// for(int i=1;i<=n;i++){
// cout<<t1[i]<<" ";
// }
//
// cout<<endl;
exinit();
// for(int i=1;i<=n;i++){
// cout<<t2[i]<<" ";
// }
// cout<<endl;
int tt;
while(m--){
cin>>op>>x;
if(op==1){
cin>>y>>tt;
exadd(x,tt);
exadd(y+1,-tt);
// for(int i=1;i<=n;i++){
// cout<<t1[i]<<" ";
// }
// cout<<endl;
// for(int i=1;i<=n;i++){
// cout<<t2[i]<<" ";
// }
// cout<<endl;
}
else{
cout<<exgetsum(x,x)<<endl;
}
}
return 0;
}