这是一个可持久化线段树的练习题..

题意:

给你一个图,每次询问求边权在[l,r]之间的方案数

强制在线

做法:

有点非常可怕的可持久化线段树..

我们开个可持久化线段树..每个点的值是它选没选..

每一条新的边加入我们暴力断一条旧边..复杂度是O(nm)的..

然后...就变成了线段树区间查询..

额..具体看代码好了

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int weight;
    node * l;
    node * r;
};
node b[10000005];
node * root[100005];
int top=0;
node * new_node()
{
    return &b[top++];
}
struct edge
{
    int x;
    int y;
    int weight;
    friend bool operator < (const edge &a,const edge &b)
    {
        return a.weight<b.weight;
    }
    void read()
    {
        scanf("%d%d%d",&x,&y,&weight);
        x--;
        y--;
    }
    edge (int t=0)
    {
        weight=t;
        x=0;
        y=0;
    }
};
struct edges
{
    int y;
    int id;
    int weight;
    edges * next;
};
edges * li[1005];
int tops=0;
edges * new_edge()
{
    static edges a[200005];
    return &a[tops++];
}
void inserts(int x,int y,int z,int w)
{
    edges * t=new_edge();
    t->y=y;
    t->weight=z;
    t->id=w;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y,int z,int w)
{
    inserts(x,y,z,w);
    inserts(y,x,z,w);
}
edge a[100005];
int dist[1005];
edges * father[1005];
void dfs(int x)
{
    dist[x]=1;
    edges * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (dist[t->y]==-1)
        {
            dfs(t->y);
        }
        else
        {
            father[x]=t;
        }
    }
}
void delete_edge(int x,int y)
{
    edges * t=li[x];
    if (t->y==y)
    {
        li[x]=li[x]->next;
        return;
    }
    for (;;t=t->next)
    {
        if (t->next->y==y)
        {
            t->next=t->next->next;
            return;
        }
    }
}
int n,m;
void change(node * &now,int l,int r,int k,int val)
{
    node * t=new_node();
    (*t)=(*now);
    now=t;
    t->weight+=val;
    if (l==r-1) return;
    int mid=(l+r)/2;
    if (k<mid) change(now->l,l,mid,k,val);
    else change(now->r,mid,r,k,val);
}
void build_tree(node * &now,int l,int r)
{
    now=new_node();
    now->weight=0;
    if (l==r-1)
    {
        return;
    }
    int mid=(l+r)/2;
    build_tree(now->l,l,mid);
    build_tree(now->r,mid,r);
}
int query(node * &now,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return now->weight;
    }
    int mid=(l+r)/2;
    int ans=0;
    if (l0<mid) ans+=query(now->l,l,mid,l0,r0);
    if (mid<r0) ans+=query(now->r,mid,r,l0,r0);
    return ans;
}
void try_insert_edge(int x)
{
    memset(dist,-1,sizeof(dist));
    dist[a[x].x]=0;
    dfs(a[x].x);
    if (dist[a[x].y]!=-1)
    {
        int max_val=0;
        int now=a[x].y;
        for (;;)
        {
            if (now==a[x].x) break;
            max_val=max(max_val,father[now]->weight);
            now=father[now]->y;
        }
        now=a[x].y;
        for (;;)
        {
            if (father[now]->weight==max_val) break;
            now=father[now]->y;
        }
        delete_edge(now,father[now]->y);
        delete_edge(father[now]->y,now);
        change(root[x],0,m,father[now]->id,-max_val);
    }
    insert_edge(a[x].x,a[x].y,a[x].weight,x);
    change(root[x],0,m,x,a[x].weight);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        int last_ans=0;
        tops=0;
        top=0;
        memset(li,0,sizeof(li));
        scanf("%d%d",&n,&m);
        build_tree(root[m],0,m);
        int i;
        for (i=0;i<m;i++)
        {
            a[i].read();
        }
        sort(a,a+m);
        for (i=m-1;i>=0;i--)
        {
            root[i]=root[i+1];
            try_insert_edge(i);
        }
        int q;
        scanf("%d",&q);
        for (i=0;i<q;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x-=last_ans;
            y-=last_ans;
            x=lower_bound(a,a+m,edge(x))-a;
            y=lower_bound(a,a+m,edge(y+1))-a;
            if (x!=y)
            {
                last_ans=query(root[x],0,m,x,y);
            }
            else
            {
                last_ans=0;
            }
            printf("%d\n",last_ans);
        }
    }
    return 0;
}