TJOI2012Day2解题报告

这一年的天津省选出的题还是比较复杂的，而Day2的题或许还好吧。

这第一题还算好做，只要想出了关于时间建立树状数组即可，当然运用可持久化线段树也未尝不可。具体细节看代码吧，只要想清楚了三十分钟应该能调对。需要注意的是打爆了防御的那次攻击，伤害值并不会翻倍，哪怕在这一次开始前攻击力已经大于防御力了也不会使伤害值翻倍。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 200005
#define base 1000000009
#define lowbit(x) ((x)&(-(x)))
vector<pair<int,int> > q;
vector<pair<pair<int,int>,int> > a;
int p[maxn],n,nq,s[maxn],ans;
void insert(int w,int x){
    while(w < maxn){
        s[w] += x;
        w += lowbit(w);
    }
}
int sum(int w){
    int ret = 0;
    while(w){
        ret += s[w];
        w -= lowbit(w);
        }
    return ret;
}        
int main(){
    freopen("defense.in","r",stdin);
    freopen("defense.out","w",stdout);
    scanf("%d%d",&n,&nq);
    for(int i = 1;i<=n;i++) scanf("%d",&p[i]);
    scanf("\n");
    for(int i = 1;i<=nq;i++){
        char c;
        scanf("%c",&c);
        if(c == 'A'){
            int l,r,x;
            scanf("%d%d%d\n",&l,&r,&x);
            a.push_back(make_pair(make_pair(l,i),x));
            a.push_back(make_pair(make_pair(r+1,i),-x));
            }
        else{
            int x;
            scanf("%d\n",&x);
            q.push_back(make_pair(x,i));
            }
        }
    sort(a.begin(),a.end());
    sort(q.begin(),q.end());
    vector<pair<pair<int,int>,int> >::iterator aw = a.begin();
    for(int i = 0;i<q.size();i++){
        while(aw < a.end() && (*aw).first.first <= q[i].first){
            insert((*aw).first.second,(*aw).second);
            aw++;
            }
        int l = 0,r = q[i].second;
        while(l < r){
            int m = (l + r) >> 1;
            if(sum(m) >= p[q[i].first]) r = m;
            else l = m + 1;
            }
        int ret = (2*sum(q[i].second) - sum(l))%base;
        ans = (ans + ret) % base;
        }
    printf("%d\n",ans);            
    return 0;
} 

第三题需要稍微动一下脑筋，第一个发现的是如果对于一个点，满足题设的点们应该分布在以之为中心的一个倾斜[tex]\frac{\pi}{4}[/tex]角度的一个正方形内部，由此想到将其转过来，变成我们通常看到的正方形那样。即对点(x,y)→(x+y,x-y),继续思考发现，我们只需将这些新点按照x坐标排序，然后扫一遍，找到在其上方和下方刚刚扫过的点中离它最近的两个点。判断这两个点的纵坐标与之相差是否小于等于R即可，如果小于等于R就把他俩所在的集合合并，最后求集合个数即可。用并查集维护。实现时注意，每两个点判断是否符合条件时需要验证x坐标和y坐标，具体实现可以把一个点拆分成两个点，碰到第一个点就把它加入平衡树中，以y坐标作为关键字，碰到第二个点就删除之即可。当然平衡树自然可以使用树状数组+二分+离散化代替。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define maxn 300005
#define connect(x,y) father[getfather((x))] = getfather((y))
int ans,n,r,father[maxn];
vector<pair<pair<int,int>,pair<int,int> > > point;
map<int,int> past;
map<int,int>::iterator t1,t2;
int getfather(int x){
    if(father[x] == x) return x;
    father[x] = getfather(father[x]);
    return father[x];
}
int main(){
    freopen("bomb.in","r",stdin);
    freopen("bomb.out","w",stdout);
    scanf("%d%d",&n,&r);
    memset(father,-1,sizeof(father));
    for(int i = 0;i<n;i++) father[i] = i;
    for(int i = 0;i<n;i++){
        int x0,y0;
        scanf("%d%d",&x0,&y0);
        point.push_back(make_pair(make_pair(x0+y0,1),make_pair(i,x0-y0)));
        point.push_back(make_pair(make_pair(x0+y0+r+1,-1),make_pair(i,x0-y0)));//for erasing points first
        }
    sort(point.begin(),point.end());
    for(int i = 0;i<point.size();i++){
        int x = point[i].first.first,p = point[i].first.second,w = point[i].second.first,y = point[i].second.second;
        t1 = past.find(y);
        if(p == -1){
            if((*t1).second == w) past.erase(t1);
            }
            else{
                if(t1 != past.end()){connect(w,(*t1).second);past.erase(t1);}
                else{
                    t1 =  past.upper_bound(y),t2 = past.lower_bound(y);
                    if(t1 != past.end() && ((*t1).first)-y <= r) connect(w,(*t1).second);
                        if(t2 != past.begin() && y - (*(--t2)).first <= r) connect(w,(*t2).second);
                    }    
                past.insert(make_pair(y,w));
                }
        }
    for(int i = 0;i<n;i++) ans += getfather(i) == i;
    printf("%d\n",ans);                         
    return 0;
}