测试
一些网站新功能的测试...
例题
区间修改 + 区间查询
参考代码
- 分块
- 树状数组
- 线段树
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=100005;
ll a[N],b[N],s[N];
int id[N],len;
void update(int l,int r,ll v)
{
int x=id[l],y=id[r];
if(x==y)
{
for(int i=l;i<=r;i++){a[i]+=v;s[x]+=v;}
return;
}
for(int i=l;id[i]==x;i++){a[i]+=v;s[x]+=v;}
for(int i=r;id[i]==y;i--){a[i]+=v;s[y]+=v;}
for(int i=x+1;i<y;i++){b[i]+=v;s[i]+=v*len;}
}
ll query(int l,int r)
{
int x=id[l],y=id[r];
ll res=0;
if(x==y)
{
for(int i=l;i<=r;i++)res+=a[i]+b[x];
return res;
}
for(int i=l;id[i]==x;i++)res+=a[i]+b[x];
for(int i=r;id[i]==y;i--)res+=a[i]+b[y];
for(int i=x+1;i<y;i++)res+=s[i];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
len=sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
id[i]=(i-1)/len+1;
s[id[i]]+=a[i];
}
while(m--)
{
int op,x,y;
ll k;
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
update(x,y,k);
}
else if(op==2)
{
cin>>x>>y;
cout<<query(x,y)<<'\n';
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
int c[N];
void add(int u,int v)
{
while(u<N)
{
c[u]+=v;
u+=u&-u;
}
}
int sum(int u)
{
int res=0;
while(u)
{
res+=c[u];
u-=u&-u;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
add(i,x);
}
while(m--)
{
int op,x,y;
cin>>op>>x>>y;
if(op==1)add(x,y);
else if(op==2)cout<<sum(y)-sum(x-1)<<'\n';
}
return 0;
}
#include <bits/stdc++.h>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std;
using ll=long long;
const int N=100005;
ll a[N],val[N<<2],tag[N<<2];
void gx(int u,ll v,int len){val[u]+=v*len;tag[u]+=v;}
void push_up(int u){val[u]=val[ls]+val[rs];}
void push_down(int u,int l,int r)
{
gx(ls,tag[u],mid-l+1);
gx(rs,tag[u],r-mid);
tag[u]=0;
}
void build(int u,int l,int r)
{
if(l==r){val[u]=a[l];return;}
build(ls,l,mid);
build(rs,mid+1,r);
push_up(u);
}
void update(int u,int l,int r,int x,int y,ll v)
{
if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
push_down(u,l,r);
if(x<=mid)update(ls,l,mid,x,y,v);
if(y>mid)update(rs,mid+1,r,x,y,v);
push_up(u);
}
ll query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y)return val[u];
push_down(u,l,r);
ll res=0;
if(x<=mid)res+=query(ls,l,mid,x,y);
if(y>mid)res+=query(rs,mid+1,r,x,y);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
while(m--)
{
int op,x,y;
ll k;
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
update(1,1,n,x,y,k);
}
else if(op==2)
{
cin>>x>>y;
cout<<query(1,1,n,x,y)<<'\n';
}
}
return 0;
}
按键
Ctrl + C
⌘ + C
脚注
实时编辑器
实时编辑器
function Clock(props) { const [date, setDate] = useState(new Date()); useEffect(() => { const timerID = setInterval(() => tick(), 1000); return function cleanup() { clearInterval(timerID); }; }); function tick() { setDate(new Date()); } return ( <div> <h2>It is {date.toLocaleTimeString()}.</h2> </div> ); }
结果
Loading...
窗口
http://localhost:3000
This is a browser window.