首页 > 代码库 > [poi07]mem
[poi07]mem
题意：给定点数n<=300000的一棵树，然后初始时每条边权值为1，接下来按照时间点先后顺序的n+m-1个操作，
操作有两种：
1.A a b 把a到b的边权改为0
2.W u 求1号点到u号点的路径权值和
思路：如果现在把题目简化为是在一条直线上的操作，每次在中间删除相邻边权值或者查询某个点到1号点的权值和
我们很容易想把询问离线，然后从1->n扫描1遍，然后用一个树状数组维护前缀和即可。。
到了本题利用dfs序显然就可以转化成线性模型，
具体的话
做到点u，
如果有一个操作1在(u, fa[u])的边，时间为t，那么在t时间点删除一个点
如果有一个操作2在u点，时间为t，那么就等价于查询1~u路径上的点数-t时间内删除的点数
回溯时把操作还原
code(stl)：
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 #include<algorithm> 8 #include<string> 9 #include<map> 10 #include<set> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<ctime> 15 #define x first 16 #define y second 17 #define M0(x) memset(x, 0, sizeof(x)) 18 #define vii vector<int>::iterator 19 #define vpi vector<pair<int, int> >::iterator 20 #define Inf 0x7fffffff 21 using namespace std; 22 typedef pair<int, int> pii; 23 const int maxn = 300002; 24 vector<int> e[maxn]; 25 vector<pii> q[maxn]; 26 int n, m, ans[maxn<<1]; 27 int pos[maxn<<1]; 28 29 inline void R(int &ret){ 30 ret = 0; 31 bool ok = 0; 32 for( ; ;){ 33 int c = getchar(); 34 if (c >= ‘0‘ && c <= ‘9‘) ret = (ret << 3) + (ret << 1) + c - ‘0‘, ok = 1; 35 else if (ok) return; 36 } 37 } 38 39 40 void init(){ 41 int u, v; 42 // for (int i = 1; i <= n; ++i) e[i].clear(), q[i].clear(); 43 pii tmp; 44 for (int i = 1; i < n; ++i) 45 R(u), R(v), e[u].push_back(v), e[v].push_back(u); 46 char op[10]; 47 R(m); 48 int nm = n + m - 1; 49 int n1 = 1; 50 for (int i = 1; i <= nm; ++i){ 51 scanf("%s", op); 52 if (op[0] == ‘A‘) ++n1; 53 tmp.x = i; 54 pos[i] = n1; 55 if (op[0] == ‘W‘) 56 R(u), tmp.y = -1, q[u].push_back(tmp); 57 else { 58 R(u), R(v); 59 tmp.y = v, q[u].push_back(tmp); 60 tmp.y = u, q[v].push_back(tmp); 61 } 62 } 63 // cout << n1 << endl; 64 } 65 66 int vis[maxn], s[maxn], dep[maxn]; 67 void update(int x,const int& v){ 68 for (; x<=n; x += x&(-x)) s[x] += v; 69 } 70 71 int query(int x){ 72 int res = 0; 73 for (; x>0; x -= x&(-x)) res += s[x]; 74 return res; 75 } 76 77 int ss; 78 void dfs(const int& u){ 79 vis[u] = 1; 80 for (vpi it = q[u].begin(); it != q[u].end(); ++it) 81 if (it->y != -1 && vis[it->y]) update(pos[it->x], 1); 82 for (vpi it = q[u].begin(); it != q[u].end(); ++it) 83 if (it->y == -1) ans[it->x] = dep[u] - query(pos[it->x]); 84 for (vii it = e[u].begin(); it != e[u].end(); ++it) 85 if (!vis[*it]) dep[*it] = dep[u] + 1, dfs(*it); 86 for (vpi it = q[u].begin(); it != q[u].end(); ++it) 87 if (it->y != -1 && dep[it->y] < dep[u]) update(pos[it->x], -1); 88 } 89 90 void solve(){ 91 memset(ans, -1, sizeof(int) * (n+m+10)); 92 memset(vis, 0, sizeof(int) * (n+10)); 93 memset(s, 0, sizeof(int) * (n+10)); 94 dep[1] = 0; 95 dfs(1); 96 int nm = n + m; 97 for (int i = 1; i < nm; ++i) 98 if (ans[i] >= 0) printf("%d\n", ans[i]); 99 }100 101 int main(){102 while (scanf("%d", &n) != EOF){103 init();104 solve();105 }106 return 0;107 }
code（手写链表）：
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 #include<algorithm> 8 #include<string> 9 #include<map> 10 #include<set> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<ctime> 15 #define M0(x) memset(x, 0, sizeof(x)) 16 #define Inf 0x7fffffff 17 using namespace std; 18 const int maxn = 300002; 19 struct node{ 20 int v, next; 21 } e[maxn * 3]; 22 struct qes{ 23 int v, t, next; 24 } q[maxn << 2]; 25 int n, m, ans[maxn<<1], last[maxn], lastq[maxn], tot, len; 26 int pos[maxn<<1]; 27 28 inline void R(int &ret){ 29 ret = 0; 30 bool ok = 0; 31 for( ; ;){ 32 int c = getchar(); 33 if (c >= ‘0‘ && c <= ‘9‘) ret = (ret << 3) + (ret << 1) + c - ‘0‘, ok = 1; 34 else if (ok) return; 35 } 36 } 37 38 inline void add(const int& u,const int& v){ 39 e[tot] = (node){v, last[u]}, last[u] = tot++; 40 } 41 42 inline void add_ask(const int& u,const int& v,const int& t){ 43 q[len] = (qes){v, t, lastq[u]}, lastq[u] = len++; 44 } 45 46 void init(){ 47 int u, v; 48 memset(last, -1, sizeof(last)); 49 memset(lastq, -1, sizeof(lastq)); 50 len = tot = 0; 51 for (int i = 1; i < n; ++i) 52 R(u), R(v), add(u, v), add(v, u); 53 char op[10]; 54 R(m); 55 int nm = n + m - 1; 56 int n1 = 1; 57 for (int i = 1; i <= nm; ++i){ 58 scanf("%s", op); 59 if (op[0] == ‘A‘) ++n1; 60 pos[i] = n1; 61 if (op[0] == ‘W‘) 62 R(u), add_ask(u, -1, i); 63 else { 64 R(u), R(v); 65 add_ask(u, v, i), add_ask(v, u, i); 66 } 67 } 68 // cout << n1 << endl; 69 } 70 71 int vis[maxn], s[maxn], dep[maxn]; 72 void update(int x,const int& v){ 73 for (; x<=n; x += x&(-x)) s[x] += v; 74 } 75 76 int query(int x){ 77 int res = 0; 78 for (; x>0; x -= x&(-x)) res += s[x]; 79 return res; 80 } 81 82 void dfs(const int& u){ 83 vis[u] = 1; 84 for (int p = lastq[u]; ~p; p = q[p].next) 85 if (q[p].v != -1 && vis[q[p].v]) update(pos[q[p].t], 1); 86 for (int p = lastq[u]; ~p; p = q[p].next) 87 if (q[p].v == -1) ans[q[p].t] = dep[u] - query(pos[q[p].t]); 88 for (int p = last[u]; ~p; p = e[p].next) 89 if (!vis[e[p].v]) dep[e[p].v] = dep[u] + 1, dfs(e[p].v); 90 for (int p = lastq[u]; ~p; p = q[p].next) 91 if (q[p].v != -1 && dep[q[p].v] < dep[u]) update(pos[q[p].t], -1); 92 } 93 94 void solve(){ 95 memset(ans, -1, sizeof(int) * (n+m+10)); 96 memset(vis, 0, sizeof(int) * (n+10)); 97 memset(s, 0, sizeof(int) * (n+10)); 98 dep[1] = 0; 99 dfs(1);100 int nm = n + m;101 for (int i = 1; i < nm; ++i) 102 if (ans[i] >= 0) printf("%d\n", ans[i]); 103 }104 105 int main(){106 // freopen("a.in", "r", stdin);107 // freopen("a.out", "w", stdout);108 while (scanf("%d", &n) != EOF){109 init();110 solve();111 }112 return 0;113 }
[poi07]mem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。