蔬菜派送网站怎么做,upyun for wordpress,视频直播网站架构,在家做私房菜的网站liu_runda出的题再次$\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%$ 任 题解 题目中为什么反复强调简单路径,没有环 没有环的图中点数-边数联通块数 前缀和维护边的前缀和,和点的前缀和, 在维护边的前缀和不好维护转化为横着边前缀和,竖着边前缀和 注意边的边界问题 看边如何维护 就拿… liu_runda出的题再次$\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%\%$ 任 题解 题目中为什么反复强调简单路径,没有环 没有环的图中点数-边数联通块数 前缀和维护边的前缀和,和点的前缀和, 在维护边的前缀和不好维护转化为横着边前缀和,竖着边前缀和 注意边的边界问题 看边如何维护 就拿我的举例 你在当前为边且当前左面为边时置为1 那么当你统计答案时 ll biabianheng[x2][y2]-bianheng[x1-1][y2]-bianheng[x2][y1]bianheng[x1-1][y1]; 思考我们统计答案时要把x2相连的边切断 类似的,我们维护竖着的边时也要类似操作 代码 #includebits/stdc.h
using namespace std;
#define ll int
#define A 2101
char s[A][A];
ll vis[A][A],stax[4200000],stay[4200000],dian[A][A],bianheng[A][A],bianshu[A][A];
ll cnt0,n,m,q;
const ll nowx[5]{0,0,0,1,-1};
const ll nowy[5]{0,1,-1,0,0};
void dfs(ll x,ll y,ll x1,ll y1,ll x2,ll y2){vis[x][y]cnt;
// printf(x%lld y%lld vis%lld\n,x,y,vis[x][y]);for(ll i1;i4;i){ll xnowxnowx[i],ynowynowy[i];if(xnowx2||xnowx1) continue;if(ynowy2||ynowy1) continue;if(s[xnow][ynow]-00) continue;if(vis[xnow][ynow]) continue;dfs(xnow,ynow,x1,y1,x2,y2);}
}
void bfs(ll x1,ll y1,ll x2,ll y2){cnt0;for(ll ix1;ix2;i)for(ll jy1;jy2;j){if(s[i][j]1!vis[i][j]){cnt;dfs(i,j,x1,y1,x2,y2);}}for(ll ix1;ix2;i)for(ll jy1;jy2;j){vis[i][j]0;}printf(%d\n,cnt);
}
int main(){scanf(%d%d%d,n,m,q);for(ll i1;in;i){scanf(%s,s[i]1);}
// memset()for(ll i1;in;i)for(ll j1;jm;j){if(s[i][j]1s[i][j-1]1){bianheng[i][j];}if(s[i][j]1s[i-1][j]1){bianshu[i][j];}if(s[i][j]1){dian[i][j];}}for(ll i1;in;i)for(ll j1;jm;j){bianheng[i][j]bianheng[i][j]bianheng[i-1][j]bianheng[i][j-1]-bianheng[i-1][j-1];bianshu[i][j]bianshu[i][j]bianshu[i-1][j]bianshu[i][j-1]-bianshu[i-1][j-1];dian[i][j]dian[i][j]dian[i-1][j]dian[i][j-1]-dian[i-1][j-1];}
// for(ll i1;in;i,puts())
// for(ll j1;jm;j){
// printf(bian%d ,bianheng[i][j]);
// }for(ll i1,x1,x2,y1,y2;iq;i){scanf(%d%d%d%d,x1,y1,x2,y2);ll biabianheng[x2][y2]-bianheng[x1-1][y2]-bianheng[x2][y1]bianheng[x1-1][y1];
// printf(%d %d %d %d bia%d\n,bianheng[x2][y2],bianheng[x1-1][y2],bianheng[x2][y1],bianheng[x1-1][y1-1],bia);biabianshu[x2][y2]-bianshu[x1][y2]-bianshu[x2][y1-1]bianshu[x1][y1-1];
// printf(%d %d %d %d bia%d\n,bianshu[x2][y2],bianshu[x1][y2],bianshu[x2][y1-1],bianshu[x1-1][y1-1],bia);ll diadian[x2][y2]-dian[x1-1][y2]-dian[x2][y1-1]dian[x1-1][y1-1];printf(%d\n,dia-bia);}
} 飞 题解 其实就是求逆序对,然而逆序对是$n*log$的并不能过,思考优化 我们发现其实它给了多段等差数列, 先看所有等差数列都是完整的情况 我们在同一段等差数列上可以由$x[i-1]$推到$x[i]$思考我们找的是比当前大的个数,$x[i]x[i-1]a$所有之前等差数列贡献都要减一 那么设之前贡献$tmp$得到当前贡献$tmp-cnt(等差数列个数)$ 那么我们思考$a$(即等差数列首项)怎么维护,我们拿一个树状数组维护$a$的所有值 假设当前值为$x$那么逆序对数就是$i-sum(x)-1$ 然后我们考虑第一段不是完整的 假设当前$x$转移到$x2$中$x,x2$都比$begin$小那么等差数列上所有小于$begin$贡献都要减一(头一段上没有处于$x$--$x2$数不能转移) 若当前已经比$begin$大了把它当成一个正常等差数列 代码 #includebits/stdc.h
using namespace std;
#define ll long long
#define A 111111
ll c[A];
ll tus,n,a,mod,now,cnt0,ans0,last,tmp;
void add(ll x,ll u){for(ll ix;ia;ii-i)c[i]u;
}
ll sum(ll x){ll ans0;for(ll ix;i1;i-i-i)ansc[i];return ans;
}
int main(){scanf(%lld%lld%lld%lld,n,tus,a,mod);ll nowtus;if(tusa){add(tus1,1);}for(ll i2;in;i){now(anow)%mod;if(nowa){tmpi-sum(now1)-1;cnt;add(now1,1);}else{tmp-cnt;if(nowtus) tmp;}anstmp;}printf(%lld\n,ans);
} 转载于:https://www.cnblogs.com/znsbc-13/p/11366198.html
