T1：【p3792】由乃与大母神原型
线段树维护区间min、区间max、区间和、区间平方和。 通过min和max算出，如果是连续段、‘和’和‘平方和’应该是多少。 类似hash的思想。但平方和可能被卡，可以用立方和处理。
线段树维护区间min、区间max、区间和、区间平方和。
通过min和max算出，如果是连续段、‘和’和‘平方和’应该是多少。
类似hash的思想。但平方和可能被卡，可以用立方和处理。
#include #include #include #include #include<string> #include #include #include #include using namespace std; typedef long long ll; /*【p3792】由乃...（lxl果然毒瘤...） 1.单点修改；2.查询区间l、r是否可以重排为值域上连续的一段。*/ //线段树维护区间min、区间max、区间和、区间平方和。 //通过min和max算出，如果是连续段、‘和’和‘平方和’应该是多少。 //类似hash的思想。但平方和可能被卡，可以用立方和处理。 void reads(ll &x){ //读入优化（正负整数） ll f=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x*=f; //正负号 } struct node{ double max; ll ans; }seg[500019]; const ll N=500019,mod=1000000007; ll n,m,op,x,y,a[N]; inline ll cube(ll x){return x*x%mod*x%mod;} //立方 inline ll sqr(ll x){return x*x%mod;} //平方 ll Min[N<<2],Sum[N<<2]; //区间最小值，区间立方和 inline void push_up(ll rt) { Min[rt]=min(Min[rt<<1],Min[rt<<1|1]),Sum[rt]=(Sum[rt<<1]+Sum[rt<<1|1])%mod; } inline void build(ll rt,ll l,ll r){ if(l==r){Min[rt]=a[l],Sum[rt]=cube(a[l]);return;} ll mid=(l+r)>>1; build(rt<<1,l,mid),build(rt<<1|1,mid+1,r); push_up(rt); } inline void update(ll rt,ll l,ll r,ll p,ll x){ if(l==r){Min[rt]=x,Sum[rt]=cube(x);return;} ll mid=(l+r)>>1; if(p<=mid) update(rt<<1,l,mid,p,x); else update(rt<<1|1,mid+1,r,p,x); push_up(rt); } inline ll Query_Min(ll rt,ll l,ll r,ll ql,ll qr){ if(l>=ql&&r<=qr) return Min[rt]; ll mid=(l+r)>>1; if(qr<=mid) return Query_Min(rt<<1,l,mid,ql,qr); else if(ql>mid) return Query_Min(rt<<1|1,mid+1,r,ql,qr); else return min(Query_Min(rt<<1,l,mid,ql,qr),Query_Min(rt<<1|1,mid+1,r,ql,qr)); } inline ll Query_Sum(ll rt,ll l,ll r,ll ql,ll qr){ if (l>=ql&&r<=qr) return Sum[rt]; ll mid=(l+r)>>1; if (qr<=mid) return Query_Sum(rt<<1,l,mid,ql,qr); else if (ql>mid) return Query_Sum(rt<<1|1,mid+1,r,ql,qr); else return (Query_Sum(rt<<1,l,mid,ql,qr)+Query_Sum(rt<<1|1,mid+1,r,ql,qr))%mod; } ll sum2[N],sum3[N]; //前缀平方、立方和，便于比较 int main(){ reads(n),reads(m); for(ll i=1;i<=n;i++) reads(a[i]); build(1,1,n); //↓↓预处理区间前缀平方、立方和，便于比较 for(int i=1;i<=n;i++) sum2[i]=(sum2[i-1]+sqr(i))%mod, sum3[i]=(sum3[i-1]+cube(i))%mod; while(m--){ reads(op),reads(x),reads(y); if(op==1){ update(1,1,n,x,y); continue; } ll Minn=Query_Min(1,1,n,x,y),Summ=Query_Sum(1,1,n,x,y); ll Sums=((y-x+1)*cube(Minn)%mod+sum3[y-x] //连续段的立方和 +(y-x+1)*(y-x)/2%mod*3*Minn%mod*Minn%mod+sum2[y-x]*3%mod*Minn%mod)%mod; (Sums==Summ)?puts("damushen"):puts("yuanxing"); } }
T2：
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号