平湖网站开发,企业培训师资格证报考2022,网站建设要求,wordpress ajax请求Lawn of the Dead
题意#xff1a;
有一个N * M的方格#xff0c;我们从(1,1)出发#xff0c;只能向右走或者向下走#xff0c;存在一些障碍#xff0c;问有多少格子是我们所能到达的 2n,m,k1e5
题解#xff1a;
所有的点减去不能到达的点的个数#xff0c;…Lawn of the Dead
题意
有一个N * M的方格我们从(1,1)出发只能向右走或者向下走存在一些障碍问有多少格子是我们所能到达的 2n,m,k1e5
题解
所有的点减去不能到达的点的个数就是可以到达的点的个数 有障碍的地方不能达到而我们只能向右向下走当某个点的左边和上边都是不可达时该点就不可达并会对自己的右边的点和下方的点造成影响 n,m,k1e5空间很大但是地雷数目有限我们可以从上往下逐行对每一行的地雷排序后处理对于每个地雷找到从自己的右上角点(x-1,y1)开始从左往右的连续不可达区间的范围那么x这行的这个范围也不可达我们可以用线段树来实现区间的查询与维护。处理每一行累加后用总点数减去即可 官方代码中将可以到达的区域赋值1每次找第x-1行区间内最最左侧的1然后将第x行这段区间赋值为1剩下0即为不可到达区域
代码
md调了半天还是不对 2021/7/30 0:41 问题解决现在代码对了睡觉
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
#define ls (rt1)
#define rs ((rt1)|1)
typedef long long ll;
using namespace std;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn3e59;
int n,m,k;
vectorintvec[maxn];
struct tree{int l,r;int lazy;int sum;
}tr[2][maxn];
void pushup(int op,int rt){tr[op][rt].sumtr[op][ls].sumtr[op][rs].sum;
}
void solve(int op,int rt,int val){tr[op][rt].sum(tr[op][rt].r-tr[op][rt].l1)*val;tr[op][rt].lazyval;
}
void pushdown(int op,int rt){solve(op,ls,tr[op][rt].lazy);solve(op,rs,tr[op][rt].lazy);tr[op][rt].lazy-1;
}
void build(int op,int rt,int l,int r){tr[op][rt].ll;tr[op][rt].rr;if(lr){tr[op][rt].sum0;tr[op][rt].lazy-1;return ;}int midlr1;build(op,ls,l,mid);build(op,rs,mid1,r);pushup(op,rt);
}
void update(int op,int rt,int L,int R,int v){if(Ltr[op][rt].r||Rtr[op][rt].l)return ;if(Ltr[op][rt].ltr[op][rt].rR){solve(op,rt,v);return ;}if(tr[op][rt].lazy!-1)pushdown(op,rt);update(op,ls,L,R,v);update(op,rs,L,R,v);pushup(op,rt);
}
int query(int op,int rt,int L,int R){if(!tr[op][rt].sum)return INF_int;if(Ltr[op][rt].r||Rtr[op][rt].l)return INF_int;if(tr[op][rt].ltr[op][rt].r)return tr[op][rt].l;if(tr[op][rt].lazy!-1)pushdown(op,rt);if(Ltr[op][rt].ltr[op][rt].rR){if(tr[op][ls].sum0)return query(op,ls,L,R);else return query(op,rs,L,R);}return min(query(op,ls,L,R),query(op,rs,L,R));
}
void init(){for(int i1;in;i)vec[i].clear();memset(tr,0,sizeof(tr));
}
int main()
{//freopen(1008.in,r,stdin);int tread();while(t--){scanf(%d%d%d,n,m,k);init();for(int i1;ik;i){int x,y;scanf(%d%d,x,y);vec[x].push_back(y);}build(0,1,1,m);build(1,1,1,m);update(1,1,1,1,1);int op0;ll ans0;for(int i1;in;i){int L0;sort(vec[i].begin(),vec[i].end());int pos;for(int y:vec[i]){if(y-1L1){posquery(op^1,1,L1,y-1);if(pos!INF_int)update(op,1,pos,y-1,1);}Ly; }if(L1m){posquery(op^1,1,L1,m);if(pos!INF_int)update(op,1,pos,m,1);}anstr[op][1].sum;update(op^1,1,1,m,0);op^1;}printf(%lld\n,ans);}return 0;
}
官方代码
#includebits/stdc.h
using namespace std;
#define ls (x1)
#define rs (x1|1)
const int N 1e5 5;
const int inf 0x3f3f3f3f;
vectorinte[N];
int tr[2][N 2], lz[2][N 2];void push_down(int f, int x, int l, int r, int mid) {if (lz[f][x] -1)return;tr[f][ls] lz[f][x] * (mid - l 1);tr[f][rs] lz[f][x] * (r - mid);lz[f][ls] lz[f][rs] lz[f][x];lz[f][x] -1;
}
void update(int f,int x, int l, int r, int L, int R, int v) {if (L l R r) {tr[f][x] (r - l 1) * v;lz[f][x] v;return;}int mid (l r) 1;push_down(f, x, l, r, mid);if (R mid)update(f, ls, l, mid, L, R, v);else if (L mid)update(f, rs, mid 1, r, L, R, v);else {update(f, ls, l, mid, L, mid, v);update(f, rs, mid 1, r, mid 1, R, v);}tr[f][x] tr[f][ls] tr[f][rs];
}
int query(int f, int x, int l, int r, int L, int R) {if (!tr[f][x])return inf;if (l r)return l;int mid l r 1;push_down(f, x, l, r, mid);if (L l R r) {if (tr[f][ls] 0) return query(f, ls, l, mid, L, R);else return query(f, rs, mid 1, r, L, R);}else {if (R mid)return query(f, ls, l, mid, L, R);else if (L mid)return query(f, rs, mid 1, r, L, R);else return min(query(f, ls, l, mid, L, mid), query(f, rs, mid 1, r, mid 1, R));}
}
int main() {int T;scanf(%d, T);while (T--) {int n, m, k;scanf(%d %d %d, n, m, k);for (int i 1; i n; i)e[i].clear();for (int i 1; i (m 2); i) {tr[0][i] tr[1][i] 0;lz[0][i] lz[1][i] -1;}for (int i 0; i k; i) {int x, y;scanf(%d %d, x, y);e[x].push_back(y);}long long ans 0;update(0, 1, 1, m, 1, 1, 1);for (int x 1; x n; x) {int l 0;sort(e[x].begin(), e[x].end());for (auto y : e[x]) {if (y - 1 l 1) {int pos query((x 1) ^ 1, 1, 1, m, l 1, y - 1);if (pos ! inf)update(x 1, 1, 1, m, pos, y - 1, 1);}l y;}if (l 1 m) {int pos query((x 1) ^ 1, 1, 1, m, l 1, m);if (pos ! inf)update(x 1, 1, 1, m, pos, m, 1);}ans tr[x 1][1];update((x 1) ^ 1, 1, 1, m, 1, m, 0);}printf(%lld\n, ans);}return 0;
}
