F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 4785 >> 新人求助,树状数组那道题,luoguAC,bzojCE
assass_cannotin @ 2018-07-12 20:43:41
[ Quote ] [ Edit ] [ Delete ] 1#
如题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
int s=0,w=1;
char c=nc();
while(!isdigit(c)){if(c=='-')w=-1;c=nc();}
while(isdigit(c)){s=(s<<3)+(s<<1)+c-'0',c=nc();}
x=s*w;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
typedef long long ll;
const int mod=998244353,MAXN=100010;
inline int quick_pow(int a,int b)
{
int res=1;
for(;b;b>>=1)
{
if(b&1)res=1LL*a*res%mod;
a=1LL*a*a%mod;
}
return res;
}
inline int inv(int x){return quick_pow(x,mod-2);}
inline int merge(int a,int b){return (1LL*(1+mod-a)*b%mod+1LL*(1+mod-b)*a%mod)%mod;}
int n,m;
struct _2D_Tree
{
int Root;
int ls[MAXN*360],rs[MAXN*360],val[MAXN*360],seg,rt[MAXN<<4],_2D_seg,_2D_ls[MAXN<<2],_2D_rs[MAXN<<2];
inline void modify(int &root,int L,int R,int l,int r,int x)
{
if(!root)root=++seg;
if(l<=L&&r>=R)
{
val[root]=merge(val[root],x);
return ;
}
int mid=(L+R)>>1;
if(r<=mid)modify(ls[root],L,mid,l,r,x);
else if(l>mid)modify(rs[root],mid+1,R,l,r,x);
else modify(ls[root],L,mid,l,mid,x),modify(rs[root],mid+1,R,mid+1,r,x);
}
inline int query(int root,int L,int R,int x)
{
if(!root)return 0;
if(L==R)return val[root];
int mid=(L+R)>>1;
if(x<=mid)return merge(val[root],query(ls[root],L,mid,x));
else return merge(val[root],query(rs[root],mid+1,R,x));
}
inline void _2D_modify(int &root,int xL,int xR,int xl,int xr,int yl,int yr,int x)
{
if(!root)root=++_2D_seg;
if(xl<=xL&&xr>=xR)
{
modify(rt[root],1,n,yl,yr,x);
return ;
}
int mid=(xL+xR)>>1;
if(xr<=mid)_2D_modify(_2D_ls[root],xL,mid,xl,xr,yl,yr,x);
else if(xl>mid)_2D_modify(_2D_rs[root],mid+1,xR,xl,xr,yl,yr,x);
else _2D_modify(_2D_ls[root],xL,mid,xl,mid,yl,yr,x),_2D_modify(_2D_rs[root],mid+1,xR,mid+1,xr,yl,yr,x);
}
inline int _2D_query(int root,int xL,int xR,int x,int y)
{
if(!root)return 0;
if(xL==xR)return query(rt[root],1,n,y);
int mid=(xL+xR)>>1;
if(x<=mid)return merge(query(rt[root],1,n,y),_2D_query(_2D_ls[root],xL,mid,x,y));
else return merge(query(rt[root],1,n,y),_2D_query(_2D_rs[root],mid+1,xR,x,y));
}
}T;
struct Tree
{
int ls[MAXN<<2],rs[MAXN<<2],seg,rt,val[MAXN<<2];
inline void modify(int &root,int L,int R,int l,int r,int x)
{
if(!root)root=++seg;
if(l<=L&&r>=R)
{
val[root]=merge(val[root],x);
return ;
}
int mid=(L+R)>>1;
if(r<=mid)modify(ls[root],L,mid,l,r,x);
else if(l>mid)modify(rs[root],mid+1,R,l,r,x);
else modify(ls[root],L,mid,l,mid,x),modify(rs[root],mid+1,R,mid+1,r,x);
}
inline int query(int root,int L,int R,int x)
{
if(!root)return 0;
if(L==R)return val[root];
int mid=(L+R)>>1;
if(x<=mid)return merge(val[root],query(ls[root],L,mid,x));
else return merge(val[root],query(rs[root],mid+1,R,x));
}
}S;
int opt,l,r;
int main()
{
read(n),read(m);
for(register int i=1;i<=m;i++)
{
read(opt),read(l),read(r);
if(opt==1)
{
int p=inv(r-l+1);
if(l>1)
T._2D_modify(T.Root,1,n,1,l-1,l,r,p),S.modify(S.rt,1,n,1,l-1,1);
if(r<n)
T._2D_modify(T.Root,1,n,l,r,r+1,n,p),S.modify(S.rt,1,n,r+1,n,1);
T._2D_modify(T.Root,1,n,l,r,l,r,2LL*p%mod);
S.modify(S.rt,1,n,l,r,1LL*(r-l)*p%mod);
}
else
{
if(l==1)write(merge(1,S.query(S.rt,1,n,r)));
else write(merge(1,T._2D_query(T.Root,1,n,l-1,r)));
putchar(10);
}
}
}
walker90 @ 2018-07-12 20:44:38
[ Quote ] [ Edit ] [ Delete ] 2#
前排%%%%天下第一神犇zcy
coldhac @ 2018-07-12 21:00:09
[ Quote ] [ Edit ] [ Delete ] 3#
前排%%%%天下第一神犇zcy
assass_cannotin @ 2018-07-12 21:02:57
[ Quote ] [ Edit ] [ Delete ] 4#
@lavendir
Cydiater @ 2018-07-12 21:42:11
[ Quote ] [ Edit ] [ Delete ] 5#
BZOJ 老问题了,数组开太大会 CE。
RBQ @ 2018-07-12 21:53:18
[ Quote ] [ Edit ] [ Delete ] 6#
BZOJ为了防止卡评测强行限制编译时间,于是你数组开太大的话,会导致编译超时。也就是返回CE。
(一般出这种问题是你数组大小卡内存限制或者已经MLE了,BZOJ内存测的是静态申请+动态申请大小,洛谷测的是实际使用大小)
assass_cannotin @ 2018-07-12 22:08:47
[ Quote ] [ Edit ] [ Delete ] 7#
问题已解决,谢谢大家
assass_cannotin @ 2018-07-12 22:08:57
[ Quote ] [ Edit ] [ Delete ] 8#
修改了数组大小
[Top] [Previous Page] [Next Page]

HOME Back