小白月赛86

D.dfs

问图中有多少个长方形，正方形也算长方形，并且每个长方形都是当前区域最大的。

判断长方形可以计算连通块面积s，以及横坐标之差最大值mx，纵坐标之差最大值my，如果mx*my=s则是长方形。

int xm[4]={1,0,-1,0};
int ym[4]={0,-1,0,1};
int mxx,mxy,mnx,mny,sum;
void dfs(int x,int y,int n,int m){
	vis[x][y]=1;
	sum+=1;
	mxx=max(mxx,x);
	mxy=max(mxy,y);
	mnx=min(mnx,x);
	mny=min(mny,y);
	rep(i,0,3){
		int xx=x+xm[i],yy=y+ym[i];
		if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]||vis[xx][yy])continue;
		dfs(xx,yy,n,m);
	}
}
void solve(void){ 
	int n,m,ans=0;
	cin>>n>>m;
	rep(i,1,n)
		rep(j,1,m){
			char t;
			cin>>t;
			if(t=='*')a[i][j]=1;
		}
	rep(i,1,n)
		rep(j,1,m){
			if(a[i][j]==0&&vis[i][j]==0){
				mxx=mnx=i;
				mxy=mny=j;
				sum=0;
				dfs(i,j,n,m);
//				cout<<i<<' '<<j<<'\n';
//				cout<<mxx<<' '<<mnx<<' '<<mxy<<' '<<mny<<' '<<sum<<'\n';
//				cout<<ans<<'\n'<<'\n';
				if((mxx-mnx+1)*(mxy-mny+1)==sum)ans++;
			}
		}
	cout<<ans<<'\n';
}

E.可口蛋糕

每个蛋糕都有饱腹值和美味值，选择一个连续区间内的蛋糕，使饱腹值大于W，美味值尽可能大。看题解似乎可以写滑窗，但是不会啊，还是遍历一侧边界+lower_bound好写

遍历左边界，对于每个左边界i，用Lower_bound找第一个使区间饱腹值大于等于W的右边界j，再在[j,n]里选一个右边界使得[i,j]内美味值最大。可以先进行一个前缀和预处理，那么寻找j就转化为在[j,n]里选一个j，使得pre[j]最大。

暴力寻找是O(n)的，显然不可以。但这个东西就是维护区间最大值，也可以先预处理，只不过是从后往前维护。

ll wpre[N],dpre[N],dmx[N]; 
void solve(void){ 
	int n;
	ll W,ans=-1e18;
	cin>>n>>W;
	rep(i,1,n)cin>>w[i],wpre[i]=wpre[i-1]+w[i];
	rep(i,1,n)cin>>d[i],dpre[i]=dpre[i-1]+d[i];
    dmx[n+1]=-1e15;
	rep1(i,n,1)dmx[i]=max(dmx[i+1],dpre[i]);//预处理[i,n]内的dpre最大值
	rep(i,1,n){
		int j=lower_bound(wpre+1,wpre+1+n,wpre[i-1]+W)-wpre;//寻找j下界
		ans=max(ans,dmx[j]-dpre[i-1]);//查表找到[j,n]内dpre最大值
	}
	cout<<ans;
}

F.set维护区间

对于给定数列内，所有升序且每次加一的序列[i,j]，维护一个sum=sigma((j-i+1)^2)，后续会有1e5次单点修改，每次修改后都要查询sum。

首先可以转化为差分数组，升序且每次加一转化成差分后等价于：第一个数随意，后面有一段连续的1。每次修改时，观察差分数组中目标位置的值，如果修改前为1，说明修改前是一个目标序列的一部分，修改后会把它断开，如果修改后为1，说明修改会把两段连上。

但只有差分数组，我们只能知道这次修改的性质，而不能知道修改后sum的变化，因为我们不知道修改影响的全1区间的首尾位置。对此我们可以再开一个set<pii>，每个元素存区间的左右端点，每次修改时直接用lower_bound就能查找到受影响的的区间。

具体来说，如果修改前是1，修改点x位于一个目标区间(l,r)内，修改后会形成(l,x-1),(x,r)两个新区间，如果修改后是1，修改点x位于一个区间(x,r)内，(x,r)左侧的区间为(l,x-1)，修改后会形成一个新区间(l,r)。每次修改后都更新set，差分数组以及sum

这种做法的巧妙之处在于所有区间的左端点l构成了一个升序序列，所有区间在set内也是升序排列的，因此用Lower_bound可以快速查到目标区间，并且返回的区间的前一个区间，就是该区间的左侧区间。

set<pii>s;
ll sum;
void add(int x,int y){//插入区间
	s.insert({x,y});//更新set和sum
	sum+=(y-x+1)*(y-x+1);
}
void del(int x,int y){
	s.erase({x,y});
	sum-=(y-x+1)*(y-x+1);
}
void update(int x,int w){//把区间更新变成两次单点更新
	if(x==1||x==n+1||w==0)return;
    //如果更新的是第一个位置或者尾部后一个，只会影响原始元素绝对大小
    //不会影响相对大小，对要维护的升序序列无意义
	dif[x]+=w;
	if(dif[x]==1){//修改后为1，连上
		auto t1=*s.lower_bound({x,-1});
		auto t2=*prev(s.lower_bound({x,-1}));
		int r=t1.second,l1=t2.first;
		del(x,r);
		del(l1,x-1);
		add(l1,r);//x所在区间和前一个区间连上了
	}
	else if(dif[x]-w==1){//修改后为1，拆开
		auto  t=*prev(s.lower_bound({x,-1}));
		int l=t.first,r=t.second;
		del(l,r);
		add(l,x-1);
		add(x,r);
	}
}
void solve(void){ 
	cin>>n>>m;
	rep(i,1,n){
		cin>>a[i];
		dif[i]=a[i]-a[i-1];
	}
	rep(i,1,n){//初始化
		int j=i+1;
		while(dif[j]==1&&j<=n)j++;
		j--;
		add(i,j);//将初始序列的目标区间插入
		i=j; 
	}
	rep(i,1,m){
		int l,r,w;
		cin>>l>>r>>w;//区间加转化为差分数组上两个单点修改
		update(l,w);
		update(r+1,-w);
		cout<<sum<<'\n';
	}
}