| 12163370 | 2014-08-16 17:03:17 | 藍雪 | Count on a tree II | accepted | 40.95 | 73M | C++
4.3.2
|
四千大大神威<(_ _)>
經四千大大指導>w<
終於突破各種WA
超級有成就感的><
總之這題就是
把樹攤開後，把每個區間射到一個平面上，然後用平方分解的方式遍歷，可以保證複雜度在O(n*q^0.5)
是說還有看到強制在線的題目QQ 好可怕><
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<cmath>
#define NN 40005
#define QQ 100005
using namespace std;
void assertTLE(bool check){
if(check == false)
while(1);
return;
}
void assertRE(bool check){
if(check == false)
printf("%d\n", 1/0);
return;
}
const int INFVAL = 100000000;
class RMQ{
public:
RMQ(){};
void setup(int _n, int *a){
all = _n;
/*printf("\nRMQ SETUP:\n");
for(int lx = 0;lx < _n;lx++)
printf("%d ", a[lx]);
puts("");*/
for(int lx = 0;lx < _n;lx++) value[lx] = a[lx];
for(int lx = 0;lx < _n;lx++) sp[lx][0] = lx;
for(int lx = 1;(1<<lx) < (_n+2);lx++){
for(int ly = 0;ly+(1<<lx)-1 < _n;ly++){
int m = ly + (1<<(lx-1));
sp[ly][lx] = minindex(sp[ly][lx-1], sp[m][lx-1]);
}
}
return;
}
int ask(int a, int b){
if(b < a) a^=b^=a^=b;
//assertRE(a<=b);
int k = (int)(log2(b-a+1));
//assertRE(a+(1<<k) - 1 >= b - (1<<k));
assertRE(a+(1<<k) - 1 <= b);
return minindex(sp[a][k], sp[b-(1<<k)+1][k]);
}
private:
int sp[8*NN][50];
int value[8*NN];
int all;
int minindex(int ind1, int ind2){
return (value[ind1]<value[ind2])? ind1: ind2;
}
};
int an[NN];
int tree[NN*2];
int tlca[NN*8];
int thei[NN*8];
int nodhei[NN];
int n, sqrtn; int tlcalen = 0;
pair<int,int> nodmap[NN];
int lcamap[NN];
typedef struct _query{ int x, y; int id;int ans;int na, nb;}query;
//void printq(query a){printf("q: nod=%d->%d rang=%d->%d\n",a.na, a.nb, a.x, a.y);return;}
query qs[QQ];
bool operator<(query a, query b){
if(a.x/sqrtn != b.x/sqrtn) return a.x/sqrtn < b.x/sqrtn;
return a.y < b.y;
}
struct _cmp_id{bool operator()(query a, query b){return a.id<b.id;}}cmp_id;
vector<int> link[NN];
RMQ LCA;
int _dfscnt = 0;
void dfs(int fat, int chd){
//printf("%d ", chd+1);
nodmap[chd].first = _dfscnt;
tree[_dfscnt++] = chd;
lcamap[chd] = tlcalen;
tlca[tlcalen++] = chd;
for(int lx = 0;lx < link[chd].size();lx++){
if(fat == link[chd][lx]) continue;
nodhei[link[chd][lx]] = nodhei[chd]+1;
dfs(chd, link[chd][lx]);
tlca[tlcalen++] = chd;
//printf("%d ", chd+1);
}
nodmap[chd].second = _dfscnt;
tree[_dfscnt++] = chd;
//printf("%d ", chd);
return;
}
//set<int>nodvis;
//map<int, int>valcnt;
bool nodvis[NN];
int valcnt[NN], valsz;
int autolca = -1;
int segleft = 0, segright = 0;
void init(int _n){
valsz = 0;
for(int lx = 0;lx < NN;lx++){
nodvis[lx] = false;
valcnt[lx] = 0;
}
return;
}
void writelca(int anc){ autolca = anc; return;}
void write(int a){
//printf("visit %d, val = %d\n", a, an[a]);
//assertRE(an[a]<=40000);
if(nodvis[a] == false){
nodvis[a] = true;
valcnt[an[a]]++;
if(valcnt[an[a]] == 1) valsz++;
}else{
nodvis[a] = false;
assertRE(valcnt[an[a]] > 0);
valcnt[an[a]]--;
if(valcnt[an[a]] == 0){
valsz--;
}
}
return;
}
int read(){
/*printf("read seg => lca = %d\n", autolca);
for(int lx = 0;lx < 10;lx++)
if(valcnt[lx] != 0)
printf("getval = %d\t", lx);
printf("\n");*/
int _sz = valsz;
if(autolca != -1)
_sz += valcnt[an[autolca]]==0;
return _sz;
}
int main()
{
int n, m;scanf("%d %d", &n, &m);
map<int, int> jizz;
for(int lx = 0;lx < n;lx++)
scanf("%d", an+lx);
// jizzan
for(int lx = 0;lx < n;lx++){
if(jizz.count(an[lx]) == 0){
int gtsz = jizz.size();
jizz[an[lx]] = gtsz;
an[lx] = gtsz;
}else
an[lx] = jizz[an[lx]];
//printf("%d ", an[lx]);
}
//printf("\n");
for(int lx = 0;lx < n-1;lx++){
int a,b;scanf("%d %d", &a,&b);
link[a-1].push_back(b-1);
link[b-1].push_back(a-1);
}
_dfscnt = 0;
nodhei[0] = 0;
dfs(-1, 0);
for(int lx = 0;lx < tlcalen;lx++)
thei[lx] = nodhei[tlca[lx]];
LCA.setup(tlcalen, thei);
/*printf("\npair result:\n");
for(int lx = 0;lx < n;lx++)
printf("%d -> %d, %d\n", lx, nodmap[lx].first, nodmap[lx].second);*/
for(int lx = 0;lx < m;lx++){
int na, nb;scanf("%d %d", &na, &nb); na--; nb--;
qs[lx].id = lx; qs[lx].na = na, qs[lx].nb = nb;
//printf("ask %d,%d -> %d,%d\n", nodmap[na].first, nodmap[na].second, nodmap[nb].first, nodmap[nb].second);
if((nodmap[na].first < nodmap[nb].first) and (nodmap[nb].second < nodmap[na].second)){
qs[lx].x = nodmap[na].first, qs[lx].y = nodmap[nb].first;
//printf("trig1\n");
}else if((nodmap[nb].first < nodmap[na].first) and (nodmap[na].second < nodmap[nb].second)){
qs[lx].x = nodmap[nb].first, qs[lx].y = nodmap[na].first;
//printf("trig2\n");
}else if(nodmap[na].second < nodmap[nb].first){
qs[lx].x = nodmap[na].second, qs[lx].y = nodmap[nb].first;
//printf("trig3\n");
}else if(nodmap[nb].second < nodmap[na].first){
qs[lx].x = nodmap[nb].second, qs[lx].y = nodmap[na].first;
//printf("trig4\n");
}else if(na == nb){
qs[lx].x = nodmap[nb].first, qs[lx].y = nodmap[nb].second;
}
}
//assertTLE(m >= 1);
sqrtn = (int)(n/sqrt(m));
sort(qs, qs+m);
init(n);
/*for(int lx = 0;lx < m;lx++)
printq(qs[lx]);*/
for(int lx = qs[0].x;lx <= qs[0].y;lx++)
write(tree[lx]);
writelca(tlca[LCA.ask(lcamap[qs[0].na], lcamap[qs[0].nb])]);
segleft = qs[0].x, segright = qs[0].y;
qs[0].ans = read();
for(int lxx = 1;lxx < m;lxx++){
if(segleft < qs[lxx].x){
for(int lx = segleft;lx <= qs[lxx].x-1;lx++){
write(tree[lx]);
}
}else if(segleft > qs[lxx].x){
for(int lx = segleft-1;lx >= qs[lxx].x;lx--){
write(tree[lx]);
}
}
if(segright < qs[lxx].y){
for(int lx = segright+1;lx <= qs[lxx].y;lx++){
write(tree[lx]);
}
}else if(segright > qs[lxx].y){
for(int lx = segright;lx >= qs[lxx].y+1;lx--){
write(tree[lx]);
}
}
segleft = qs[lxx].x, segright = qs[lxx].y;
writelca(tlca[LCA.ask(lcamap[qs[lxx].na], lcamap[qs[lxx].nb])]);
qs[lxx].ans = read();
}
sort(qs, qs+m, cmp_id);
for(int lx = 0;lx < m;lx++){
//printq(qs[lx]);
printf("%d\n", qs[lx].ans);
}
return 0;
}
/*
testdata:
8
5
1 3 4 -1 2 1 2 9
1 2 2 3 3 4
1 5 5 6
5 7 7 8
2 6
3 6
1 8
3 7
1 6
*/
沒有留言:
張貼留言