점분 치 와 점분 수
254002 단어 데이터 구조
토로
제목
충격파
구유
작년 에 은퇴 시 켜 준 좋 은 물건.한 문 제 를 쓰 고 나 면 내 가 이미 동태 적 으로 분 리 를 할 수 있다 고 생각 하 는 나 는 정말 too young too simple, sometimes naive. 지금 은 적어도 작년 처럼 머리 를 쥐 어 뜯 고 템 플 릿 을 쓰 지 않 는 다.그러나 거 위 는 나의 작은 bug 더미 에 영향 을 주지 않 는 다.이 배열 은 경 계 를 넘 었 습 니 다. 그곳 은 비우 지 않 았 습 니 다. 그곳 은 변수 가 바 뀌 었 습 니 다.
제목.
[IOI2011]Race
내 마음 을 무 너 뜨리 는 좋 은 본보기.더 이상 평범 할 수 없 는 분할 치료 양식 이지 만 거 위 는 죽어도 조절 할 수 없다.코드 를 재 구성 하 는 것 은 그래도 마지막 에 어떻게 고 치 는 지 나 도 어디로 가 야 할 지 모 르 겠 어.대략 d [0] 는 n 과 tot - sz [x] 로 부 여 됩 니 다.이 거 교 는 아들 과 나의 sz 의 크기 관 계 를 직접 판단 하여 아들 의 실제 sz 를 얻 었 다.どこでもドア
//Achen
#include
",ans);
Formylove;
}
cf716 E. Digit Tree
............................................................................................
경 로 를 반 으로 나 누 면 l v 는 8727 ° 1 0 d e p r + r v. 1. ( m o d p ) lv*10^{dep_r}+rv \equiv 0\ (mod\ p) lv∗10depr+rv≡0 (mod p) 전형 점.(p, 10) = 1 exgcd 로 10 의 역 원 을 구하 라 고 합 니 다.
//Achen
#include
",ans);
Formylove;
}
cf293 E. Close Vertices
.................................................................................1 차원 정렬 더 블 포인터 1 차원 트 리 배열 하면 됩 니 다.작은 틀
//Achen
#include
",ans);
Formylove;
}
충격파
등...........................................................................포인터 동적 할당 메모리 트 리 배열 도 너무 좋 죠?근 데 조회 할 때 는 up 과 min 을 가 져 가 야 돼 요. 안 그러면 RE 잖 아 요!그리고 나 에 게 나무 에 있 는 모든 조상 과 내 가 그들 에 게 가 는 거 리 를 기록 하 세 요. 예전 에 나 는 lca 에 게 거 리 를 찾 아 달라 고 썼 습 니 다. 바보 가 아 닙 니까?각각 두 개의 나무 모양 의 배열 에 서브 트 리 안의 점 을 담 고 하 나 는 자신의 거 리 를 누 르 고 하 나 는 자신의 점 에 따라 아버지의 거 리 를 나눈다.
//Achen
#include
",rs); lastans=rs;
}
int main() {
//freopen("3730.in","r",stdin);
//freopen("3730.out","w",stdout);
read(n); read(m);
For(i,1,n) read(val[i]);
For(i,2,n) {
int u,v;
read(u); read(v);
add(u,v);
}
get_root(1,0,n);
build(1,n);
For(i,1,m) {
int op,x,y;
read(op); read(x); read(y);
x^=lastans; y^=lastans;
if(!op) Qry(x,y);
else change(x,y);
}
Formylove;
}
cf757 G. Can Bash Save the Day?
................................................................................................q 개 동작 이 있 습 니 다:
1 l r x: 문의 ∑ i = l r d i s t (p i, x) \ \ sum \ \ limits{i=l}^r dist(p_i,x) i=l∑rdist(pi,x) 2 x： s w a p ( p x , p x + 1 ) swap(p_x,p_{x+1}) swap(px,px+1)
n , q ≤ 2 × 1 0 5 n,q\le 2\times 10^5 n,q≤2×105, 강제 온라인.
강사 가 이것 은 지속 가능 한 나무 라 고 말 했 는데, 나 는 이것 이 set 물 을 건 널 수 있 지 않 겠 습 니까?그리고 즐겁게 때 리 고 즐겁게 T 를 했 어 요.각 점 은 set 로 관할 범 위 를 유지 하 는 점 이 a 의 순서 로 접두사 와 두 개의 log 이 고 70 여 개의 점 이 있 을 때 TLE 입 니 다.
//Achen
#include::iterator
LL lastans;
void qry(int ql,int qr,int x) {
LL rs=0;
For(i,0,18) if(f[x][i]) {
int y=f[x][i];
IT it=rt[y].lower_bound((node){ql,0});
if(it==rt[y].end()) continue;
if(it!=rt[y].begin()) {
--it; rs-=((*it).sum[1]+(*it).sum[0]*dis[x][i]);
if(f[x][i+1]) rs+=((*it).sum[2]+(*it).sum[0]*dis[x][i+1]);
}
it=rt[y].lower_bound((node){qr,0});
node tpp=*it;
if(it==rt[y].end()||(*it).pos>qr) {
if(it==rt[y].begin()) continue;
--it;
}
tpp=*it;
rs+=((*it).sum[1]+(*it).sum[0]*dis[x][i]);
if(f[x][i+1]) rs-=((*it).sum[2]+(*it).sum[0]*dis[x][i+1]);
}
printf("%lld
",rs); lastans=rs;
}
void change(int x) {
For(i,0,18) if(f[a[x]][i]) {
int u=f[a[x]][i];
IT it=rt[u].lower_bound((node){x});
node tp=*it;
rt[u].erase(it);
it=rt[u].lower_bound((node){x});
if(it!=rt[u].end()&&(*it).pos==x+1) {
node tp2=*it;
LL t1=tp.sum[1]-dis[a[x]][i]+tp2.sum[1]-tp.sum[1];
LL t2=tp.sum[2]-dis[a[x]][i+1]+tp2.sum[2]-tp.sum[2];
rt[u].insert((node){x,tp.sum[0],t1,t2});
}
else { tp.pos++; rt[u].insert(tp); }
}
For(i,0,18) if(f[a[x+1]][i]) {
int u=f[a[x+1]][i];
IT it=rt[u].lower_bound((node){x+1,0}),it2=it;
if(it2!=rt[u].begin()) it2--;
if((*it2).pos==x) break;
node t=*it; t.pos--;
rt[u].erase(it); rt[u].insert(t);
}
swap(a[x],a[x+1]);
p[a[x]]=x; p[a[x+1]]=x+1;
}
int main() {
//freopen("1.in","r",stdin);
//freopen("WA.out","w",stdout);
read(n); read(m);
For(i,1,n) read(a[i]),p[a[i]]=i;
For(i,2,n) {
int u,v,w;
read(u); read(v); read(w);
add(u,v,w);
}
RT=0; get_root(1,0,n);
build(RT,n);
For(i,1,m) {
int op,x,l,r;
read(op);
if(op==1) {
read(l); read(r); read(x);
l^=lastans%(1<<30); r^=lastans%(1<<30); x^=lastans%(1<<30);
qry(l,r,x);
}
else {
read(x);
x^=lastans%(1<<30);
change(x);
}
}
Formylove;
}
어 쩔 수 없어. 나 무 를 오래 갈 수 밖 에 없어...a 의 순서에 따라 지난 번 에 나 무 를 만 들 었 습 니 다. 각 점 은 현재 기여 한 점 수 를 유지 하고 아버지 와 의 거리 와 매번 체인 을 새로 만 듭 니 다.수정 은 x 라 는 나무 에 만 영향 을 주 고 앞 뒤의 나 무 는 변 하지 않 기 때문에 x - 1 을 바탕 으로 새로운 x 를 만 들 면 됩 니 다.그리고 지속 가능 해 야 하기 때문에 두 갈래 를 강제로 돌려 야 한다.밑 에서 위로 올 라 가 는 우수한 점 수 를 억지로 위 에서 아래로 나 누 는 추악 한 물건 으로 만 들 었 다.
//Achen
#include
",rs); lastans=rs%(1<<30);
}
int main() {
//freopen("std.in","r",stdin);
//freopen("WA.out","w",stdout);
read(n); read(m);
For(i,1,n) read(a[i]);
For(i,2,n) {
int u,v,w;
read(u); read(v); read(w);
son[u].push_back(MP(v,w));
son[v].push_back(MP(u,w));
}
cnt=n;
prebuild(1,0); rebuild(1);
RT=0; get_root(1,0,cnt);
rt[0]=RT; build(RT,cnt);
totnd=cnt;
For(i,1,n)
upd(rt[i],rt[i-1],0,a[i]);
int qc=0;
For(i,1,m) {
int op,x,l,r;
read(op);
if(op==1) {
read(l); read(r); read(x);
l^=lastans; r^=lastans; x^=lastans;
Qry(l,r,x);
}
else {
read(x); x^=lastans;
upd(rt[x],rt[x-1],0,a[x+1]);
swap(a[x],a[x+1]);
}
}
Formylove;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
