Nice boat
Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 968 Accepted Submission(s): 441
Let us continue our story, z*p(actually you) defeat the 'MengMengDa' party's leader, and the 'MengMengDa' party dissolved. z*p becomes the most famous guy among the princess's knight party.
One day, the people in the party find that z*p has died. As what he has done in the past, people just say 'Oh, what a nice boat' and don't care about why he died.
Since then, many people died but no one knows why and everyone is fine about that. Meanwhile, the devil sends her knight to challenge you with Algorithm contest.
There is a hard data structure problem in the contest:
There are n numbers a_1,a_2,...,a_n on a line, everytime you can change every number in a segment [l,r] into a number x(type 1), or change every number a_i in a segment [l,r] which is bigger than x to gcd(a_i,x) (type 2).
You should output the final sequence.
For each test case, the first line contains a integers n.
The next line contains n integers a_1,a_2,...,a_n separated by a single space.
The next line contains an integer Q, denoting the number of the operations.
The next Q line contains 4 integers t,l,r,x. t denotes the operation type.
T<=2,n,Q<=100000
a_i,x >=0
a_i,x is in the range of int32(C++)
Please output a single more space after end of the sequence
10
【题目大意】
给你一串数字，有两个操作，1表示把一段区间内的数变成x，2表示把一段区间内的数如果这个数大于x则变为这个数与x的最小公约数，否则不变。最后输出变化后的一组数。
【题目分析】
这题和其他线段树有一些区别，这题是在所有的处理结束后才全部输出。
我们在每个结点中加一个flag标记该区间内的数字是否都是同一个，如果区间是同一个数的话我们就可以进行批处理，这将会大大降低时间复杂度。
再用一个temp来存储该结点的val,然后在pushdown函数将temp的值一层一层的传递下去。
这里的temp既起到了该结点是否已经向下更新的作用(相当于lazy)，又起到了记录子节点需要更新的值的作用。
temp只有在val的值改变的时候才改变。
//Memory Time
// 5376K 651MS
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define MAX 100100
#define LL long long
using namespace std;
int n,m;
int ans;
int num[MAX];
struct Tree
{
int l,r;
bool flag;
int val,temp;
};
Tree tree[MAX<<2]; int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
} void pushup(int x)
{
int tmp=x<<1;
tree[x].val=max(tree[tmp].val,tree[tmp+1].val);
tree[x].flag=(tree[tmp].val==tree[tmp+1].val&&tree[tmp].flag&&tree[tmp+1].flag);
} void pushdown(int x)
{
if(tree[x].temp==-1)return;
int tmp=x<<1;
int mid=(tree[x].l+tree[x].r)>>1;
tree[tmp].val=tree[tmp+1].val=tree[tmp].temp=tree[tmp+1].temp=tree[x].temp;
tree[x].temp=-1;
} void build(int l,int r,int x)
{
tree[x].flag=0;
tree[x].temp=-1;
tree[x].l=l,tree[x].r=r;
if(l==r)
{
scanf("%d",&tree[x].val);
tree[x].flag=1;
return;
}
int tmp=x<<1;
int mid=(l+r)>>1;
build(l,mid,tmp);
build(mid+1,r,tmp+1);
pushup(x);
} void update(int l,int r,int num,int x)
{
if(r<tree[x].l||l>tree[x].r)return;
if(l<=tree[x].l&&r>=tree[x].r)
{
tree[x].flag=1;
tree[x].val=num;
tree[x].temp=num;
return;
}
pushdown(x);
int tmp=x<<1;
int mid=(tree[x].l+tree[x].r)>>1;
if(r<=mid)
update(l,r,num,tmp);
else if(l>mid)
update(l,r,num,tmp+1);
else
{
update(l,mid,num,tmp);
update(mid+1,r,num,tmp+1);
}
pushup(x);
} void change(int l,int r,int num,int x)
{
if(r<tree[x].l||l>tree[x].r)return;
if(tree[x].flag&&tree[x].val<=num)return;
if(l<=tree[x].l&&r>=tree[x].r&&tree[x].flag)
{
tree[x].val=gcd(tree[x].val,num);
tree[x].temp=tree[x].val;
return;
}
pushdown(x);
int tmp=x<<1;
int mid=(tree[x].l+tree[x].r)>>1;
if(r<=mid)
change(l,r,num,tmp);
else if(l>mid)
change(l,r,num,tmp+1);
else
{
change(l,mid,num,tmp);
change(mid+1,r,num,tmp+1);
}
pushup(x);
} void query(int l,int r,int k,int x)
{
if(k<tree[x].l||k>tree[x].r)return;
if(tree[x].flag)
{
ans=tree[x].val;
return;
}
pushdown(x);
int tmp=x<<1;
int mid=(tree[x].l+tree[x].r)>>1;
if(k<=mid)
query(l,mid,k,tmp);
else
query(mid+1,r,k,tmp+1);
} int main()
{
int T;
int t,l,r,num;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
build(1,n,1);
scanf("%d",&m);
while(m--)
{
scanf("%d %d %d %d",&t,&l,&r,&num);
if(t==1)
update(l,r,num,1);
else
change(l,r,num,1);
}
for(int i=1;i<=n;i++)
{
ans=0;
query(1,n,i,1);
printf("%d ",ans);
}
puts("");
}
return 0;
}
【解法二】
这题不知道出题人怎么搞的，数据弱爆了，直接暴力还比线段树还快。
当然也不是单纯的暴力，从后往前搜，用一个数组prime来记录需要求gcd的值，遇到type=1就退出，最后来求一下gcd即可。
//Memory Time
// 2232K 250MS
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define MAX 100100
#define LL long long
using namespace std;
int T,n,q;
int num[MAX];
int t[MAX],l[MAX],r[MAX],x[MAX];
int prime[MAX];
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
int main()
{
// freopen("cin.txt","r",stdin);
// freopen("cout.txt","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&num[i]);
scanf("%d",&q);
for(int i=1;i<=q;++i)
scanf("%d %d %d %d",&t[i],&l[i],&r[i],&x[i]);
for(int i=1;i<=n;++i)
{
int tp=num[i];
int index=-1;
for(int j=q;j>=1;--j)
{
if(i>=l[j]&&i<=r[j])
{
if(t[j]==1)
{
tp=x[j];
break;
}
else prime[++index]=x[j];
}
}
for(int j=index;j>=0;--j)
{
if(tp>prime[j])
tp=gcd(tp,prime[j]);
}
printf("%d ",tp);
}
puts("");
}
return 0;
}