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