传送门：HDU1698
题意：给定n和q个操作，每个操作为：i j k 令num[t]=k(i<=t<=j)，初始化num[t]=1(1<=t<=n)
思路：数据量较大，暴力肯定不行。考虑用线段树进行区间替换，这里询问只有一次，且是询问总区间，所以可以直接输出一号节点的信息。
代码：
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #define ll long long #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int,int>P; const int MAXN=100010; struct node{ int key,lazy;//lazy为延时标记 }num[MAXN<<2]; void pushup(int rt) { num[rt].key=num[rt<<1].key+num[rt<<1|1].key; } void pushdown(int rt,int k) { if(num[rt].lazy) { num[rt<<1].lazy=num[rt].lazy; num[rt<<1|1].lazy=num[rt].lazy; num[rt<<1].key=num[rt].lazy*(k-(k>>1)); num[rt<<1|1].key=num[rt].lazy*(k>>1); num[rt].lazy=0; } } void build(int l,int r,int rt) { num[rt].lazy=0; if(l==r) { num[rt].key=1; return ; } int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int L,int R,int x,int l,int r,int rt) { if(L<=l&&r<=R) { num[rt].lazy=x; num[rt].key=x*(r-l+1); return ; } pushdown(rt,r-l+1); int mid=(l+r)>>1; if(L<=mid)update(L,R,x,lson); if(R>mid)update(L,R,x,rson); pushup(rt); } int main() { int t,n,a,b,c,q; scanf("%d",&t); for(int Case=1;Case<=t;Case++) { scanf("%d%d",&n,&q); build(1,n,1); while(q--) { scanf("%d%d%d",&a,&b,&c); update(a,b,c,1,n,1); } printf("Case %d: The total value of the hook is %d.\n",Case,num[1].key); } return 0; }