noip模拟34(待补)

A.Merchant

B.Equation

一道简单的线段树,考场上因为忘了给子树传递信息挂没了..

B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define p() puts("")
	#define ll long long int 
	#define ull unsigend ll
	#define re register ll 
	#define lf double
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memset(x,y,sizeof x)
	inline ll read() {
		ll ss=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
		return cit?ss:-ss;
	}
} using namespace BSS;

const ll N=1e6+51;
const lf eps=1e-10;
ll m,n,ts,cnt;
ll w[N],head[N],dep[N],dfn[N],rk[N],siz[N],b[N];
lf a[15][15];
struct I { ll u,v,nxt; } e[N<<1|1];
struct II { ll lazy,sum; } tr[N*8];
inline void add(ll u,ll v){
	e[++ts].u=u;
	e[ts].v=v;
	e[ts].nxt=head[u];
	head[u]=ts;
}
inline void spread(ll x,ll l,ll r){
	if(tr[x].lazy){
		tr[x<<1].sum+=tr[x].lazy;
		tr[x<<1|1].sum+=tr[x].lazy;
		tr[x<<1].lazy+=tr[x].lazy;
		tr[x<<1|1].lazy+=tr[x].lazy;
		tr[x].lazy=0;
	}
	return ;
}
ll query(ll x,ll l,ll r,ll pos){
	if(l==r) return tr[x].sum;
	ll mid=(l+r)>>1;
	spread(x,l,r);
	if(pos<=mid) return query(x<<1,l,mid,pos);
	else return query(x<<1|1,mid+1,r,pos);
}
void update(ll x,ll l,ll r,ll ql,ll qr,ll val){
	if(l>=ql and r<=qr) {
		tr[x].sum+=val;
		tr[x].lazy+=val;
		return ;
	}
	ll mid=(l+r)>>1;
	spread(x,l,r);
	if(ql<=mid) update(x<<1,l,mid,ql,qr,val);
	if(qr>=mid+1) update(x<<1|1,mid+1,r,ql,qr,val);
	return ;
}
void dfs(ll now,ll val,ll depth){
	dfn[now]=++cnt; rk[cnt]=now;
	siz[now]=1;
	if(depth&1) b[now]=val-w[now]; // 奇数 为 -1
	else b[now]=val+w[now];
	dep[now]=depth;
	for(re i=head[now];i;i=e[i].nxt){
		dfs(e[i].v,b[now],depth+1);
		siz[now]+=siz[e[i].v];
	}
	return ;
}
void Guass(ll u,ll v,ll temp){
	if(u>v) swap(u,v);
	a[1][1]=1.0,a[1][2]=1.0,a[1][3]=temp*1.0;	
	b[u]=query(1,1,n,dfn[u]); b[v]=query(1,1,n,dfn[v]);
	if(dep[u]&1) a[2][1]=-1.0;
	else a[2][1]=1.0;
	if(dep[v]&1) a[2][2]=1.0;
	else a[2][2]=-1.0;
	a[2][3]=(b[u]-b[v])*1.0;
/*	for(re i=1;i<=2;i++){
		for(re j=1;j<=3;j++)
		printf("%.2lf ",a[i][j]);
		puts("");
	}puts("");
*/
			
	if(a[1][1]==a[2][1] and a[1][2]==a[2][2] and a[1][3]==a[2][3]){
		puts("inf"); return ;
	}
	if(a[1][1]==a[2][1] and a[1][2]==a[2][2] and a[1][3]!=a[2][3]){
		puts("none"); return ;
	}
	if(a[1][1]==-a[2][1] and a[1][2]==-a[2][2] and a[1][3]==-a[2][3]){
		puts("inf"); return ;
	}
	if(a[1][1]==-a[2][1] and a[1][2]==-a[2][2] and a[1][3]!=-a[2][3]){
		puts("none"); return ;
	}
	a[2][2]-=a[2][1]*a[1][2];
	a[2][3]-=a[2][1]*a[1][3];
	lf res=a[2][3]/a[2][2];
	if(dep[v]&1) res+=b[v];
	else res=b[v]-res;
	temp=(ll)res;
	if(res!=(ll)res) puts("none");
	else printf("%lld\n",temp);
	return ;
}
signed main(){
	n=read(); m=read();
	ll u,v,opt,temp;
	for(re i=2;i<=n;i++){
		v=read(),w[i]=read();
		add(v,i); // add(i,v);
	}
	dfs(1,0,1);
	for(re i=1;i<=n;i++){
		update(1,1,cnt,dfn[i],dfn[i],b[i]);
	}
	for(re i=1;i<=m;i++){
		opt=read();
		if(opt&1){
			u=read(),v=read();
			Guass(u,v,read());
		}
		else{
			u=read();
			if(dep[u]&1){
				update(1,1,cnt,dfn[u],dfn[u]+siz[u]-1,w[u]);
				w[u]=read();
				update(1,1,cnt,dfn[u],dfn[u]+siz[u]-1,-w[u]);
			}
			else{
				update(1,1,cnt,dfn[u],dfn[u]+siz[u]-1,-w[u]);
				w[u]=read();
				update(1,1,cnt,dfn[u],dfn[u]+siz[u]-1,w[u]);
			}
		}
	}
	return 0;
}

C.Rectangle

考场上想了很多:

  1. 考虑每个方块造成的贡献,但是转移复杂度过于巨大,且思维量和码量都很巨大,甚至还要使用容斥,于是果断放弃..
  2. 使用\(O(n^4)\)枚举每个矩形,然后在此基础上优化,使用线段树进行统计,但是并不知道如何才能使用数据结构节约复杂度..
    正解是使用枚举左右两个边界:
    我们从右往左枚举左边界,然后从左边界向右枚举右边界..
    之所以这么做,是因为中间枚举到的点会对将来的统计造成贡献,因为也会被当作边界处理..
    然后我们就得到了左边界\(L\)和右边界\(R\)..
    于是答案即为\((R-L)*\Sigma_h\)..
    考虑如何求出\(\Sigma_h\)..
    我们选择使用树状数组,维护\(sum\)和\(size\)即可..线段树常数较大,且许多\(log(M)\)皆为满,故适用树状数组..
    我们从下往上分别统计矩形的上下边界,每统计完一段区间的答案,然后移动右边界,并使右边界的点都依附到左边界即可..
上一篇:浅析 PHP 中的 Generator


下一篇:jvm java 数组 字节码