/ * 나무 하나, 많은 조작 이 있 습 니 다. (1) 변 x - y 를 삭제 하고 변 a - b 를 추가 합 니 다.(2) a - > b 의 경로 에 있 는 모든 점 권 을 x (a, b 포함) 로 변경 합 니 다.(3) a - > b 의 경로 에 있 는 모든 점 권 에 d (a, b 포함) 를 추가 합 니 다.(4) a - > b 를 조회 하 는 경로 에서 두 번 째 로 엄격 한 점 권 과 나타 나 는 횟수 (모든 값 이 똑 같 으 면 all same 을 출력 합 니 다). * /
LCT 의 템 플 릿 문제!
코드 는 다음 과 같 습 니 다:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100010;
struct Node *null;
struct Node{
Node *fa,*ch[2];
int val,size; //val ，size 。
int same,add;
int rev;
int mm,mmc;
int sm,smc;
inline void clear(int _val){ // 。
fa = ch[0] = ch[1] = null;
val = _val; size = 1;
same = -INF;
add = 0;
mm = _val; mmc = 1;
sm = -INF; smc = 0;
}
inline void add_val(int _val,int num){ // val， num
if(_val == -INF)return;
if(_val < sm)return;
if(_val == sm)smc += num;
else if(_val < mm){
sm = _val; smc = num;
}
else if(_val == mm){
mmc += num;
}
else{
sm = mm; smc = mmc;
mm = _val; mmc = num;
}
}
inline void push_up(){
size = 1 + ch[0]->size + ch[1]->size;
mm = sm = -INF;
mmc = smc = 0;
add_val(val,1);
add_val(ch[0]->mm,ch[0]->mmc);
add_val(ch[0]->sm,ch[0]->smc);
add_val(ch[1]->mm,ch[1]->mmc);
add_val(ch[1]->sm,ch[1]->smc);
}
inline void setc(Node *p,int d){
ch[d] = p;
p->fa = this;
}
inline bool d(){
return fa->ch[1] == this;
}
inline bool isroot(){
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void flip(){
if(this == null)return;
swap(ch[0],ch[1]);
rev ^= 1;
}
inline void update_add(int w){
if(this == null)return;
if(mm != -INF)mm += w;
if(sm != -INF)sm += w;
val += w;
add += w;
}
inline void update_same(int w){
if(this == null)return;
mm = w; mmc = size;
sm = -INF; smc = 0;
same = w;
val = w;
add = 0;
}
inline void push_down(){
if(same != -INF){
ch[0]->update_same(same);
ch[1]->update_same(same);
same = -INF;
}
if(add){
ch[0]->update_add(add);
ch[1]->update_add(add);
add = 0;
}
if(rev){
ch[0]->flip();
ch[1]->flip();
rev = 0;
}
}
inline void go(){
if(!isroot())fa->go();
push_down();
}
inline void rot(){
Node *f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c],c);
this->setc(f,!c);
if(ff->ch[cc] == f)ff->setc(this,cc);
else this->fa = ff;
f->push_up();
}
inline Node* splay(){
go();
while(!isroot()){
if(!fa->isroot())
d()==fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node* access(){
for(Node *p = this,*q = null; p != null; q = p, p = p->fa){
p->splay()->setc(q,1);
p->push_up();
}
return splay();
}
inline Node* find_root(){
Node *x;
for(x = access(); x->push_down(), x->ch[0] != null; x = x->ch[0]);
return x;
}
void make_root(){
access()->flip();
}
void cut(){
access();
ch[0]->fa = null;
ch[0] = null;
push_up();
}
void cut(Node *x){ // x 。
if(this == x || find_root() != x->find_root())return;
else{
x->make_root();
cut();
}
}
void link(Node *x){ // x 。（ x ）
if(find_root() == x->find_root())return;
else {
make_root(); fa = x;
}
}
};
void SAME(Node *x,Node *y,int w){ //（2）a->b x（ a，b）；
x->access();
for(x = null; y != null; x = y, y = y->fa){
y->splay();
if(y->fa == null){
y->ch[1]->update_same(w);
x->update_same(w);
y->val = w;
y->push_up();
return;
}
y->setc(x,1);
y->push_up();
}
}
void ADD(Node *x,Node *y,int w){ //（3）a->b d（ a，b）；
x->access();
for(x = null; y != null; x = y, y = y->fa){
y->splay();
if(y->fa == null){
y->ch[1]->update_add(w);
x->update_add(w);
y->val += w;
y->push_up();
return;
}
y->setc(x,1);
y->push_up();
}
}
int MM,MMC; // ，
int SM,SMC; // ，
void ADD_VAL(int val,int num){ // val， num
if(val == -INF)return;
if(val < SM)return;
if(val == SM)SMC += num;
else if(val < MM){
SM = val;
SMC = num;
}
else if(val == MM){
MMC += num;
}
else {
SM = MM; SMC = MMC;
MM = val; MMC = num;
}
}
void ask(Node *x,Node *y){ // a->b ， ；
x->access();
for(x=null; y != null; x = y, y = y->fa){
y->splay();
if(y->fa == null){
MM = SM = -INF;
MMC = SMC = 0;
ADD_VAL(y->val,1);
ADD_VAL(y->ch[1]->mm,y->ch[1]->mmc);
ADD_VAL(y->ch[1]->sm,y->ch[1]->smc);
ADD_VAL(x->sm,x->smc);
ADD_VAL(x->mm,x->mmc);
return;
}
y->setc(x,1);
y->push_up();
}
}
Node pool[MAXN],*tail;
Node *node[MAXN];
struct Edge{
int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
void init(){
tot = 0;
memset(head,-1,sizeof(head));
}
inline void addedge(int u,int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
int g[MAXN];
int fa[MAXN];
void bfs(int s){
int l,r;
g[l=r=1] = s;
fa[s] = s;
while(l <= r){
int u = g[l++];
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(v == fa[u])continue;
fa[v] = u;
node[v]->fa = node[u];
g[++r] = v;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int iCase = 0;
int n,m;
scanf("%d",&T);
while(T--){
iCase++;
printf("Case #%d:
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
