title (网站建设),seo优化的常用手法,备案要关闭网站吗,广告设计专业简历解析
写吐了…
一开始觉得线段树分治直接做就行简直是个伞兵题#xff0c;写完挂掉才想起来线段树分治会打乱操作顺序导致全假… 重构吧#xff01; 炸裂之下去贺题解#xff0c;std做法 O(mmlogm)O(m\sqrt m\log m)O(mmlogm) 令人谔谔#xff0c;但kd-tree做法确实挺…解析
写吐了…
一开始觉得线段树分治直接做就行简直是个伞兵题写完挂掉才想起来线段树分治会打乱操作顺序导致全假… 重构吧 炸裂之下去贺题解std做法 O(mmlogm)O(m\sqrt m\log m)O(mmlogm) 令人谔谔但kd-tree做法确实挺伞兵的懊恼为啥没有想到。 写完交后发现MLE成20用现成的datamaker跑个1000的数据发现就开了7e5个点 …原来矩形修改开虚点复杂度会假掉啊我直接一种植物。 重构吧 …终于过了。 思维还是要灵活这个转二维数点其实挺直观的。
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}const int N2e5100;
const double inf1e18;
const int mod998244353;inline ll ksm(ll x,ll k){ll res1;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;struct tag{ll mul,add;
}I(tag){1,0};
tag operator (const tag x,const tag y){return (tag){x.mul*y.mul%mod,(x.add*y.muly.add)%mod};
}struct pt{int x[2];
}q[N];
int num;
int F;
bool operator (const pt x,const pt y){return x.x[F]y.x[F];}
struct tree{int ch[2];int l[2],r[2];pt o;tag ans,laz;
}tr[N];
inline void pushup(int k){tr[k].l[0]tr[k].r[0]tr[k].o.x[0];tr[k].l[1]tr[k].r[1]tr[k].o.x[1];for(int o0;o1;o){int sontr[k].ch[o];if(!son) continue;for(int d0;d1;d){tr[k].l[d]min(tr[k].l[d],tr[son].l[d]);tr[k].r[d]max(tr[k].r[d],tr[son].r[d]);}}return;
}
inline void Add(int k,const tag o){if(!k) return;tr[k].anstr[k].anso;tr[k].laztr[k].lazo;
}
inline void pushdown(int k){Add(tr[k].ch[0],tr[k].laz);Add(tr[k].ch[1],tr[k].laz);tr[k].lazI;
}
int tot;
int build(int l,int r,int d){if(lr) return 0;int nowtot,mid(lr)1;Fd; nth_element(ql,qmid,qr1);tr[now].oq[mid];tr[now].anstr[now].lazI;tr[now].ch[0]build(l,mid-1,d^1);tr[now].ch[1]build(mid1,r,d^1);pushup(now);return now;
}
struct node{int l[2],r[2];
};
void upd(int k,const node o,const tag w){if(!k) return;if(o.l[0]tr[k].r[0]||o.r[0]tr[k].l[0]||o.l[1]tr[k].r[1]||o.r[1]tr[k].l[1]) return;if(o.l[0]tr[k].l[0]tr[k].r[0]o.r[0]o.l[1]tr[k].l[1]tr[k].r[1]o.r[1]){Add(k,w);return;}pushdown(k);if(o.l[0]tr[k].o.x[0]tr[k].o.x[0]o.r[0]o.l[1]tr[k].o.x[1]tr[k].o.x[1]o.r[1])tr[k].anstr[k].answ;upd(tr[k].ch[0],o,w);upd(tr[k].ch[1],o,w);
}
ll ans[N];
void getans(int k){if(!k) return;ans[tr[k].o.x[1]]tr[k].ans.add;pushdown(k);getans(tr[k].ch[0]);getans(tr[k].ch[1]);return;
}int op[N],l[N],r[N],val[N],pos[N],tim[N];
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();mread(); for(int i1;im;i){op[i]read();if(op[i]2){l[i]read();r[i]read();val[i]read();tim[i]m;}else if(op[i]3){ pos[i]read();q[num](pt){pos[i],i};}else tim[read()]i; }int rtbuild(1,num,0);for(int i1;im;i){if(op[i]2){tag wI;if(op[i]1) w.addval[i];else w.mulval[i];node o;o.l[0]l[i];o.r[0]r[i];o.l[1]i;o.r[1]tim[i];//printf(upd: (%d %d) (%d %d) mul%d add%d\n,o.l[0],o.r[0],o.l[1],o.r[1],mul,add);upd(rt,o,w);}}getans(rt);for(int i1;im;i){if(op[i]3) printf(%lld\n,ans[i]);}debug(tot%d\n,tot);return 0;
}
/**/
