【日常小测】回转寿司

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/20170623_statement.pdf

解题报告

看到这题我们不难想到分块
更进一步,对于每一个块来说,块内的数的相对大小不变
于是我们只需要用堆便可维护块内有哪些数

再稍加观察,我们发现只要再用一个堆记录块内的操作,然后从左向右扫一遍便可更新具体的数
于是我们就可以在:$O(n^{1.5} \log n)$的时间复杂度内解决这个问题了

另外priority_queue的构造函数是$O(n)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 400009;
const int M = 25009;
const int S = 1000;
const int B = N / S + 10; 

int n, sn, m, arr[N];
priority_queue<int> val[B];
vector<int> opr[B];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline void get_element(int w) {
	if (opr[w].empty()) {
		return;
	}
	priority_queue<int, vector<int>, greater<int> > heap(opr[w].begin(), opr[w].end()); 
	for (int i = max(1, w * S), lim = min((w + 1) * S - 1, n); i <= lim; i++) {
		if (arr[i] > heap.top()) {
			heap.push(arr[i]);
			arr[i] = heap.top();
			heap.pop();
		}
	}	
	opr[w].clear();
}

inline int modify_element(int w, int s, int t, int v) {
	get_element(w);
	int tmp = -1;
	for (int i = s; i <= t; i++) {
		if (v < arr[i]) {	
			tmp = arr[i];
			swap(v, arr[i]);
		}
	}
	val[w] = priority_queue<int>(arr + max(1, w * S), arr + 1 + min(n, (w + 1) * S - 1));
	return v;
}

inline int modify_block(int w, int v) {
	val[w].push(v);
	int ret = val[w].top();
	val[w].pop();
	if (v != ret) {
		opr[w].push_back(v);
	}
	return ret;
}

inline int solve(int s, int t, int v) {
	int ss = s / S, st = t / S;
	v = modify_element(ss, s, min(t, (ss + 1) * S - 1), v);
	if (ss != st) {
		for (int i = ss + 1; i < st; i++) {
			v = modify_block(i, v);
		}
		v = modify_element(st, st * S, t, v);
	}
	return v;
}

int main() {
	n = read(); m = read();
	sn = n / S;
	for (int i = 1; i <= n; i++) {
		arr[i] = read();
	}
	for (int i = 0; i <= sn; i++) {
		val[i] = priority_queue<int>(arr + max(1, i * S), arr + 1 + min(n, (i + 1) * S - 1));
	}
	for (int tt = 1; tt <= m; tt++) {
		int s = read(), t = read(), v = read();
		if (s <= t) {
			v = solve(s, t, v);		
		} else {
			v = solve(s, n, v);
			v = solve(1, t, v);
		}
		printf("%d\n", v);
	}
	return 0;
}

【日常小测】路径规划

题目大意

给定一棵$n(n \le 3 \cdot 10^5)$个点无根带边权的树
要求找出一条路径使得该路径上边权的最小值乘边权和最大

解题报告

这题啊!我们可以无脑点分对不对啊?
时间复杂度$O(n \log ^2 n)$,卡卡常数能过去

但这题更优雅的做法是维护直径
就像51nod上一个题一样,每一块内搞一个直径
合并两个块后生成的大块的直径一定在这四个点之间
于是就一路合并上去就可以辣!
时间复杂度:$O(n \log n)$

Code

点分治版本:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 300009;
const int M = N << 1;
const int INF = 1e9;
 
int n,head[N],nxt[M],to[M],cost[M];
LL vout;
 
inline void Add_Edge(int u, int v, int c) {
    static int E = 1; 
    to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
class Divide_and_Conquer{
    int rt,rt_sz,blk_sz,tot,sz[N],vis[N];
    struct Data{
        int mn,id; LL sum;
        inline bool operator < (const Data &B) const {
            return mn < B.mn;
        }
    }sta[N];
    public:
        void solve(int w, int blk) { 
            GetRoot(w, blk); vis[w=rt] = 1; tot = 0;
            for (int i=head[w];i;i=nxt[i]) {
                if (!vis[to[i]]) {
                    DFS(to[i], w, to[i], cost[i], cost[i]);
                }
            } 
            if (tot) update(); 
            for (int i=head[w];i;i=nxt[i]) {
                if (!vis[to[i]]) { 
                    if (sz[to[i]] > sz[w]) sz[to[i]] = blk - sz[w];
                    solve(to[i], sz[to[i]]);
                }
            }
        }
    private:
        inline void update() {
            sort(sta+1, sta+1+tot);
            LL mx1=0,mx2=0; int sur1=0,sur2=0;
            for (int i=tot;i;i--) {
                vout = max(vout, sta[i].mn * sta[i].sum);
                if (sur1 && sur1 != sta[i].id) {
                    vout = max(vout, (mx1 + sta[i].sum) * sta[i].mn);
                } else if (sur2 && sur2 != sta[i].id) {
                    vout = max(vout, (mx2 + sta[i].sum) * sta[i].mn);
                }
                if (sta[i].sum > mx1) {
                    if (sur1 == sta[i].id) {
                        mx1 = sta[i].sum;
                    } else {
                        mx2 = mx1; sur2 = sur1;
                        mx1 = sta[i].sum; sur1 = sta[i].id;
                    }
                } else if (sta[i].sum > mx2) {
                    if (sur1 != sta[i].id) {
                        sur2 = sta[i].id;
                        mx2 = sta[i].sum;
                    }
                }
            }
        }
        inline void GetRoot(int w, int blk) {
            rt_sz = INF; blk_sz = blk;
            GetRoot1(w, w); 
        }
        void GetRoot1(int w, int f) {
            sz[w] = 1; int mx = 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f && !vis[to[i]]) {
                    GetRoot1(to[i], w);
                    sz[w] += sz[to[i]];
                    mx = max(mx, sz[to[i]]);
                }
            }
            mx = max(mx, blk_sz - sz[w]);
            if (mx < rt_sz) rt_sz = mx, rt = w;
        }
        void DFS(int w, int f, int top, int mn, LL sum) {
        	bool tag = 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f && !vis[to[i]]) {
                    DFS(to[i], w, top, mn>cost[i]?cost[i]:(tag=0,mn), cost[i] + sum);
				}
            }
            if (!tag) return;
            sta[++tot].mn = mn; sta[tot].id = top; sta[tot].sum = sum;
        }
}DAC;
 
int main() {
    n = read();
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        Add_Edge(u, v, read());
    }
    DAC.solve(1, n);
    printf("%lld\n",vout);
    return 0;
}

维护直径版本:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009; 
const int M = N << 1;

int n,head[N],nxt[M],to[M],cost[M];
int stp[N],p[N][2],fa[N][20],anc[N];
struct Edge{int u,v,c;}e[N];
LL vout,dep[N],MX[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void DFS(int w, int f) {
	fa[w][0] = f; stp[w] = stp[f] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dep[to[i]] = dep[w] + cost[i];
			DFS(to[i], w);
		}
	}
}

inline void AddEdge(int u, int v, int c, int id) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
	e[id] = (Edge){u, v, c};
}

inline LL Dis(int u, int v) {
	if (stp[v] < stp[u]) swap(u, v); int p1 = u, p2 = v;
	for (int i=19;~i;i--) if (stp[fa[v][i]]>=stp[u]) v = fa[v][i];
	if (u == v) return dep[p2] - dep[u];
	for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return -(dep[fa[u][0]]<<1) + dep[p1] + dep[p2];
}

int find(int x) {return anc[x]==x?x:anc[x]=find(anc[x]);}

inline LL Merge(int u, int v) {
	static LL ret, p1, p2; u = find(u); v = find(v);
	if (MX[u] > MX[v]) ret = MX[u], p1 = p[u][0], p2 = p[u][1];
	else ret = MX[v], p1 = p[v][0], p2 = p[v][1]; 
	for (int i=0;i<=1;i++) {
		for (int j=0;j<=1;j++) {
			LL cur = Dis(p[u][i], p[v][j]);
			if (cur > ret) {
				ret = cur; 
				p1 = p[u][i];
				p2 = p[v][j];
			}
		}
	}
	anc[u] = v; MX[v] = ret;
	p[v][0] = p1; p[v][1] = p2;
	return ret;
}

int main() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read(), i);
	} 
	DFS(1, 1);
	for (int j=1;j<20;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	sort(e+1, e+N, [](const Edge &A, const Edge &B){return A.c > B.c;});
	for (int i=1;i<=n;i++) {
		anc[i] = i;
		p[i][0] = p[i][1] = i;
	}	
	for (int i=1;i<n;i++) {
		LL tmp = Merge(e[i].u, e[i].v);
		vout = max(vout, tmp * e[i].c);
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 4326】[NOIP2015] 运输计划

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4326

这货的做法就是二分之后,用DFS序判断一下
然而这货居然卡常…….
其实是↑上面这个纸张不会用指针 ╮(╯▽╰)╭
用了加强的流读入才能在UOJ上A
另外前排膜拜Menci,指针用得贼溜:https://oi.men.ci/noip2015-transport/

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000+9;
const int M = N << 1;

int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //getchar->read
    inline void read1(int &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(ll &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(double &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (ch=='.'){
            double tmp=1;
            for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
        }
        if (bo)x=-x;
    }
    inline void read1(char *s){
        char ch=getchar();
        for (;blank(ch);ch=getchar());
        for (;!blank(ch);ch=getchar())*s++=ch;
        *s=0;
    }
    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
    //scanf->read
    inline void read2(int &x){scanf("%d",&x);}
    inline void read2(ll &x){
        #ifdef _WIN32
            scanf("%I64d",&x);
        #else
        #ifdef __linux
            scanf("%lld",&x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void read2(double &x){scanf("%lf",&x);}
    inline void read2(char *s){scanf("%s",s);}
    inline void read2(char &c){scanf(" %c",&c);}
    inline void readln2(char *s){gets(s);}
    //fwrite->write
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    //puts->write
    char Out[OUT_SIZE],*o=Out;
    inline void print1(int x){
        static char buf[15];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(int x){print1(x);*o++='\n';}
    inline void print1(ll x){
        static char buf[25];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(ll x){print1(x);*o++='\n';}
    inline void print1(char c){*o++=c;}
    inline void println1(char c){*o++=c;*o++='\n';}
    inline void print1(char *s){while (*s)*o++=*s++;}
    inline void println1(char *s){print1(s);*o++='\n';}
    inline void println1(){*o++='\n';}
    inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
    struct puts_write{
        ~puts_write(){flush1();}
    }_puts;
    inline void print2(int x){printf("%d",x);}
    inline void println2(int x){printf("%d\n",x);}
    inline void print2(char x){printf("%c",x);}
    inline void println2(char x){printf("%c\n",x);}
    inline void print2(ll x){
        #ifdef _WIN32
            printf("%I64d",x);
        #else
        #ifdef __linux
            printf("%lld",x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void println2(ll x){print2(x);printf("\n");}
    inline void println2(){printf("\n");}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};

inline void Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}	

void DFS(int w, int f) {
	fa[w][0] = f; 
	in[w] = ++div_cnt;
	dep[w] = dep[f] + 1; 
	for (register int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			dis[to[i]] = dis[w] + cost[i];
			sur[to[i]] = cost[i];
			DFS(to[i], w);
		} 
	}
	out[w] = div_cnt;
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (register int j=19;~j;j--) {
		if (dep[fa[u][j]] >= dep[v]) {
			u = fa[u][j];
		}
	}
	if (u == v) return v;
	for (register int j=19;~j;j--) {
		if (fa[u][j] != fa[v][j]) {
			u = fa[u][j];
			v = fa[v][j];
		}
	}
	return fa[u][0];
}

inline bool judge(int lim) {
	memset(delta,0,sizeof(delta));
	int cnt = 0, MN = 0, MX = 0;
	for (register int i=1;i<=m;i++) {
		if (q[i].len > lim) {
			cnt++;
			MN = max(MN, q[i].len - lim);
			delta[q[i].lca] -= 2;
			delta[q[i].u] ++;
			delta[q[i].v] ++;
		}
	}
	for (register int i=n;i;i--) 
		delta[i] += delta[i+1];
	
	for (register int i=1;i<=n;i++) {
		if (delta[in[i]] - delta[out[i]+1] >= cnt) {
			MX = max(sur[i], MX);
		}
	}
	return MX >= MN;
}

int main(){
	using namespace fastIO;
	int l=0,r=0,mid,ret;
	read(n); read(m);
	for (int i=1,u,v,w;i<n;i++) {
		read(u); read(v); read(w);
		l = max(l, w);
		Add_Edge(u, v, w);
	}
	DFS(1,1);
	for (int j=1;j<=19;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	for (int i=1,u,v,lca;i<=m;i++) {
		read(u); read(v); lca = LCA(u, v);
		q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
		r = max(r, q[i].len);
		q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
	}
	
	l = r - l; ret = r;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1; 
	}
	printf("%d\n",ret);
	return 0;
}

—– UPD 2016.11.11 —–
找高一神犇学习了一下fread的使用技巧,现在最大的一个点只用500ms辣!

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 300000+9;
const int M = N << 1;
 
int head[N],to[M],nxt[M],cost[M],sur[M],delta[N];
int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

inline char Read(){
	static const int BUF_SIZE = 1000000; 
	static char buf[BUF_SIZE],*p1=0,*p2=0;
    if (p1 == p2){
    	p1=buf; p2=buf+fread(buf,1,BUF_SIZE,stdin);
		if (p2==p1) return -1;
    } return *p1++;
} 

inline int read(){
	char c=Read(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=Read();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=Read();}
	return ret*f;
}

inline void Add_Edge(int u, int v, int w) {
    static int T = 0;
    to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
    to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}   
 
void DFS(int w, int f) {
    fa[w][0] = f; 
    in[w] = ++div_cnt;
    dep[w] = dep[f] + 1; 
    for (register int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            dis[to[i]] = dis[w] + cost[i];
            sur[to[i]] = cost[i];
            DFS(to[i], w);
        } 
    }
    out[w] = div_cnt;
}
 
inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (register int j=19;~j;j--) {
        if (dep[fa[u][j]] >= dep[v]) {
            u = fa[u][j];
        }
    }
    if (u == v) return v;
    for (register int j=19;~j;j--) {
        if (fa[u][j] != fa[v][j]) {
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}
 
inline bool judge(int lim) {
    memset(delta,0,sizeof(delta));
    int cnt = 0, MN = 0, MX = 0;
    for (register int i=1;i<=m;i++) {
        if (q[i].len > lim) {
            cnt++;
            MN = max(MN, q[i].len - lim);
            delta[q[i].lca] -= 2;
            delta[q[i].u] ++;
            delta[q[i].v] ++;
        }
    }
    for (register int i=n;i;i--) 
        delta[i] += delta[i+1];
     
    for (register int i=1;i<=n;i++) {
        if (delta[in[i]] - delta[out[i]+1] >= cnt) {
            MX = max(sur[i], MX);
        }
    }
    return MX >= MN;
}
 
int main(){
    int l=0,r=0,mid,ret;
    n = read(); m = read();
    for (int i=1,u,v,w;i<n;i++) {
        u = read(); v = read(); w = read();
        l = max(l, w);
        Add_Edge(u, v, w);
    }
    DFS(1,1);
    for (int j=1;j<=19;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    for (int i=1,u,v,lca;i<=m;i++) {
        u = read(); v = read(); lca = LCA(u, v);
        q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
        r = max(r, q[i].len);
        q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
    }
     
    l = r - l; ret = r;
    while (l <= r) {
        mid = l + r >> 1;
        if (judge(mid)) ret = mid, r = mid - 1;
        else l = mid + 1; 
    }
    printf("%d\n",ret);
    return 0;
}

【BZOJ 4523】[Cqoi2016] 路由表

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4523
数据生成器:http://paste.ubuntu.com/23140079/

这个题,Trie树的做法很显然,可以持久,也可以不持久
但此题卡常QAQ
在BZOJ上过的不算,是男人就上Super OJ去交
我被逼着优化成了BZOJ上的Rank11才在SOJ上刚好卡过 (╯‵□′)╯︵┻━┻

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int M = 33000000;

int Stack[N];
bool ip[40];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Trie{
	#define TRE Trie
	int tot=1,ch[M][2],cnt,root=1,end[M];
	
	inline void modify(int len){
		int w = root; 
		for (int i=1;i<=len;i++) {
			int c = ip[i];
			if (ch[w]) w = ch[w];
			else w = ch[w] = ++tot;
		}
		end[w] = ++cnt;
	}
	
	inline int query(int l, int r){
		int top = 0, w = root, t = 1;
		while (w) {
			if (end[w]) {
				while (top && Stack[top] > end[w]) top--;
				Stack[++top] = end[w];
			}	
			w = ch[w][ip[t]]; t++;
		} t = 0;
		for (int i=1;i<=top;i++) 
			if (Stack[i] > r) break;
			else if (Stack[i] >= l) t++;
		return t;
	}
};

inline void Get_IP(){
	memset(ip,0,sizeof(ip));
	for (int j=1,sta=9;j<=4;j++,sta+=8) {
		int TP = read(), i = 1;
		while (TP) ip[sta-i] = TP & 1, TP >>= 1, i++; 
	}
}

int main(){
	for (int k=read(),a,b;k;k--) {
		char c=getchar(); 
		while (c != 'A' && c != 'Q') c=getchar();
		if (c == 'A') {
			Get_IP();
			TRE::modify(read());
		} else {
			Get_IP();
			a = read(); b = read();
			printf("%d\n",TRE::query(a,b));
		}
	}
	return 0;
}