24小时学会网站建设下载,淘宝店铺网站建设可行性报告,宿舍管理系统,服装网站建设项目实施报告前言
话说昨晚写题的时候贼NMNMNM惊险#xff0c;最后22秒把程序交了上去竟然过了 正题
题目链接:https://cometoj.com/contest/58/problem/D?problem_id2758 题目大意 nnn个点mmm条单向边#xff0c;然后每次询问一个区间[L,R][L,R][L,R]求若只选择这个区间的点#xf…前言
话说昨晚写题的时候贼NMNMNM惊险最后22秒把程序交了上去竟然过了 正题
题目链接:https://cometoj.com/contest/58/problem/D?problem_id2758 题目大意
nnn个点mmm条单向边然后每次询问一个区间[L,R][L,R][L,R]求若只选择这个区间的点求所有不能直接到达其他任何点的点权之和。 解题思路
对于每个点我们一定可以确定一个区间[li,ri][l_i,r_i][li,ri]表示若选择了这个区间以外的就无法获得这个点的权值。
那么我们对于询问区间[L,R][L,R][L,R]可以获得点xxx的权值有如下要求
包含点xxxlilt;Ll_ilt;LliL且Rlt;riRlt;r_iRri
那么我们可以大致将一个点xxx的权值分为两个区间li1,xl_i1,xli1,x和x,ri−1x,r_i-1x,ri−1。那么只要左端点在左区间右端点在右区间那么就可以获得这个点的权值。
那么我们将询问区间按照RRR以升序排序然后扫到一个右区间的左端点就将左区间整个加上对应点的权值扫到一个右区间的右端点就将左区间减去对应的权值即可。然后每次取LLL位置的值就好了。我们用树状数组进行维护即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e6100;
struct seq_node{int l,r,w;
};
struct que_node{int l,r,id;
}q[N];
int n,m,t,ans[N],c[N],l[N],r[N],cxk[N];
long long answer;
vectorseq_node v[N];
int lowbit(int x)
{return x(x^(x-1));}
void change(int x,int num)
{int ix;while(in){c[i]num;ilowbit(i);}
}
int getsum(int x)
{int sum0;while (x0){sumc[x];x-lowbit(x);}return sum;
}
bool cmp(que_node x,que_node y)
{return x.ry.r;}
int main()
{scanf(%d%d%d,n,m,t);for(int i1;in;i)l[i]0,r[i]n1,scanf(%d,cxk[i]);for(int i1;im;i){int x,y;scanf(%d%d,x,y);if(yx) r[x]min(r[x],y);else l[x]max(l[x],y);}for(int i1;it;i){scanf(%d%d,q[i].l,q[i].r);q[i].idi;}for(int i1;in;i){v[i].push_back((seq_node){l[i]1,i,cxk[i]});v[r[i]].push_back((seq_node){l[i]1,i,-cxk[i]});} sort(q1,q1t,cmp);int L1;for(int i1;it;i){while(Lq[i].r){for(int j0;jv[L].size();j){change(v[L][j].l,v[L][j].w);change(v[L][j].r1,-v[L][j].w);}L;}ans[q[i].id]getsum(q[i].l);}for(int i1;it;i)answer^(long long)i*ans[i];printf(%lld,answer);
}
