Brief description :

动态维护一组描述，每一个条目表示区间 [l, r] 内一共有 s 个石子。
如果同前面的描述矛盾则忽略，统计所有矛盾描述的总数。

Analyse :

设计一组并查集，将所有可以计算出答案的点用合并起来，根结点放再最左边，对于每一个询问如果在一个集合中则查询 S[r].s – S[l].s 即可。
…
至于维护的部分，需要画图。（注意考察有向线段，或者直接写一种情况然后另一种情况取反直接写也行。。）

#include 
using namespace std;

const int N = 200001;

struct ufs{
    int p, s;
} S[N];

int l, ll, r, rr, s;
int n, m;
int ans;


void Make(int x){
    S[x].p = x; S[x].s = 0;
}

int Find(int x){
    if (S[x].p!=x) {
        int p = S[x].p;
        S[x].p = Find(p);
        S[x].s += S[p].s;
    }
    return S[x].p;
}

void Union(int x, int y, int s){
    S[x].s = s;
    S[x].p = y;
}



int main(){
    while (cin >> n >> m){
        ans = 0;
        for (int i=0;i<=n;i++)
            Make(i);

        for (int i=0;i> l >> r >> s; l--;
            ll = S[Find(l)].p; rr = S[Find(r)].p;

            if (ll==rr){
                if (S[r].s-S[l].s!=s) ans++;
            }
            else {
                if (ll



External link :
经典并查题... 你可以在很多地方找到类似思想的题目提交。

http://acm.hit.edu.cn/judge/show.php?Proid=2844

http://hi.baidu.com/%D3%EE%D6%C7%B2%A8%B4%F8%B9%B7/blog/item/be3030e7dec85526b938209b.html
                                                												

													Posted by 
													xiaodao													
													Category: 													日常