Codeforces398D Instant Messanger

題目鏈接

是的真相就是耍流氓暴力！！！

離線處理

處理出每個點的點度deg[i](無重邊)

維護一個數組from_small[i]，表示與i相鄰的點中點度比deg[i]小的點的在線數量

然後對於每個詢問，暴力數出i的相鄰點中點度比deg[i]大的點在線的數量，然後加上from_small[i]，就是答案

復雜度是O(操作數*sqrt(點度之和))

證明：

每次詢問的復雜度為O(1) + O(遍歷度數比deg[i]大的鄰點)

設度數比deg[i]大的鄰點有x個

此時有deg[i] >= x

所以i和他的鄰點度數和至少為x*(x+1)，

因為 sigma(deg[i]) <= 2*E (E為不重疊的邊數)

所以滿足deg[j] >= deg[i]的鄰點的個數最多為sqrt(2*E)

證畢

然後其他操作的復雜度也類似，此處略過

#include 
#include 
#include 
#include 
using namespace std;

#define snuke(it,x) for (__typeof((x).begin()) it = (x).begin(); \
                it != (x).end(); it ++)

typedef pair PII;
const int N = 55555;
const int Q = 255555;
const int M = 401000;

char op[Q];
int qa[Q],qb[Q],ua[M],ub[M];
int from_small[N],n,m,nq,deg[N],on,first_on[N],edge_state[M],dot_state[N];
vector edge;
vector G[N];


int get_edge_id(PII z) {
        if (z.first>z.second) swap(z.first,z.second);
        return lower_bound(edge.begin(),edge.end(),z)-edge.begin();
}

void modify_dot(int u,int st) {
        dot_state[u] = st;
        int dt = st==1 ? 1 : -1;
        snuke(it,G[u]) {
                int v = it->first;
                int id = it->second;
                if (!edge_state[id]) continue;
                from_small[v] += dt;
        }
}

void modify_edge(int u,int v,int st) {
        int id = get_edge_id(PII(u,v));
        edge_state[id] = st;
        if (deg[u]>deg[v]) swap(u,v);
        if (dot_state[u]==1) {
                from_small[v] += st==1 ? 1 : -1;
        }
}

int query_dot(int u) {
        int ret = from_small[u];
        snuke(it,G[u]) {
                int v = it->first;
                int id = it->second;
                if (edge_state[id]==0) continue;
                ret += dot_state[v];
        }
        return ret;
}

void work() {
        sort(edge.begin(),edge.end());
        edge.erase(unique(edge.begin(),edge.end()),edge.end());
        int sz = (int)edge.size();
        for (int i = 0; i < sz; i ++) {
                deg[edge[i].first] ++;
                deg[edge[i].second] ++;
        }

        for (int i = 0; i < sz; i ++) {
                int u = edge[i].first;
                int v = edge[i].second;
                if (deg[u]>deg[v]) swap(u,v);
                G[u].push_back(PII(v,i));
        }

        for (int i = 0; i < m; i ++) {
                int id = get_edge_id(PII(ua[i],ub[i]));
                edge_state[id] = 1;
        }

        for (int i = 0; i < on; i ++) {
                modify_dot(first_on[i],1);
        }

        for (int i = 0; i  < nq; i ++) {
                int u = qa[i];
                int v = qb[i];
                if (op[i]=='O') {
                        modify_dot(u,1);
                } else if (op[i]=='F') {
                        modify_dot(u,0);
                } else if (op[i]=='A') {
                        modify_edge(u,v,1);
                } else if (op[i]=='D') {
                        modify_edge(u,v,0);
                } else {
                        printf("%d\n",query_dot(u));
                }
        }
}

int main() {
        scanf("%d%d%d",&n,&m,&nq);
        scanf("%d",&on);
        for (int i =0 ; i < on; i ++) {
                scanf("%d",&first_on[i]); first_on[i] --;
        }
        for (int  i = 0; i < m; i ++) {
                scanf("%d%d",&ua[i],&ub[i]); ua[i] --; ub[i] --;
                if (ua[i]>ub[i]) swap(ua[i],ub[i]);
                edge.push_back(PII(ua[i],ub[i]));
        }
        for (int i = 0; i < nq; i ++) {
                char s[3];
                scanf("%s",s);
                op[i] = s[0];
                if (op[i]=='A' || op[i]=='D') {
                        scanf("%d%d",&qa[i],&qb[i]); qa[i] --; qb[i] --;
                        if (qa[i]>qb[i]) swap(qa[i],qb[i]);
                        edge.push_back(PII(qa[i],qb[i]));
                } else {
                        scanf("%d",&qa[i]); qa[i] --;
                }
        }
        work();
        return 0;
}