3443: 装备合成
Time Limit: 15 Sec Memory Limit: 128 MB
Submit: 63 Solved: 31Description
【背景】lll6924在某游戏中有n件装备。【描述】游戏*有m种属性，装备有属性加成。当将A装备合成到B装备上时，A装备消失，B装备的所有小于A装备的属性更新为A装备的这个属性。然而lll6924的记性不太好，因为装备很多，所以一些属性常常记错，他在合成时会突然想起，某个装备的某个属性的初始值应该是多少（暂且认为修改后是正确的，这个属性可能会被修改多次）（请注意，这是理解题意的难点，请结合样例）。在合成过程中lll6924想知道一些装备的一些属性（根据之前给出的数据（初始属性、合成、修改），输出装备当前认为是正确的属性）。Input
输入有n+1+q行，第一行有三个用空格隔开的正整数n、m、q，q表示操作（合成操作、询问操作和修改操作）数。接下来的n行，每行有m个用空格隔开的正整数，表示这个装备的各个属性。接下来的q行，每行格式为“k a b c”，若k为1，则为将第a个装备合成到第b个装备，输入数据保证a、b装备存在，此时c=0。若k为2，则为询问第a个装备的第b个属性（若第a个装备已被合成掉，则输出该装备在被合成前的第b个属性是多少），此时c=0。若k为3，则为将第a个装备的第b个属性的初始值更新为c（注意，若a装备已被合成掉，该操作仍然有效，会影响他合成到的装备的属性）。Output
输出如输入格式所述，每个输出占一行。Sample Input
3 5 10
1 2 3 4 3
0 0 0 0 0
2 0 0 0 0
1 1 2 0
2 2 3 0
3 2 4 5
1 2 3 0
3 1 3 2
2 3 1 0
3 3 1 0
2 3 1 0
2 3 4 0
2 2 3 0Sample Output
3
2
1
5
2
【数据范围及约定】
100%的数据，0＜n≤1500,0＜m≤400，0＜q≤200000，0≤装备属性≤50000。HINT
Source
【分析】
突然爱上可以离线的题。。
【上面那题强制在线spaly还不会做啊啊啊
这题，跟BZOJ2333差不多啊，就是先把树建出来，然后弄dfs序，再用线段树维护。
建树就是按时间顺序，两个合并的时候弄一个新的点，询问的时候就问新的这个点。
T了之后乱开数组范围了ORZ。。【发现我数组范围永远开不对。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 1000010
#define Mn 1010 int a[Maxn],pos[Maxn],b[Maxn];
int rt[Mn],ft[Mn],add[Mn];
int sq; bool cmp(int x,int y) {return x>y;} void upd(int x)
{
for(int i=ft[x];i<=rt[x];i++) b[i]=a[i];
sort(b+ft[x],b++rt[x],cmp);
} void change(int x,int y,int c)
{
if(pos[x]==pos[y])
{
for(int i=x;i<=y;i++) a[i]+=c;
upd(pos[x]);
}
else
{
for(int i=x;i<=rt[pos[x]];i++) a[i]+=c;
for(int i=ft[pos[y]];i<=y;i++) a[i]+=c;
for(int i=pos[x]+;i<pos[y];i++) add[i]+=c;
upd(pos[x]);upd(pos[y]);
}
} int ffind(int x,int y)
{
int l=ft[x],r=rt[x];
if(b[l]+add[x]<y) return ;
while(l<r)
{
int mid=(l+r+)>>;
if(b[mid]+add[x]>=y) l=mid;
else r=mid-;
}
return l-ft[x]+;
} int query(int x,int y,int c)
{
int ans=;
if(pos[x]==pos[y])
{
for(int i=x;i<=y;i++) if(a[i]+add[pos[i]]>=c) ans++;
}
else
{
for(int i=x;i<=rt[pos[x]];i++) if(a[i]+add[pos[x]]>=c) ans++;
for(int i=ft[pos[y]];i<=y;i++) if(a[i]+add[pos[y]]>=c) ans++;
for(int i=pos[x]+;i<pos[y];i++) ans+=ffind(i,c);
}
return ans;
} int main()
{
int n,q;
scanf("%d%d",&n,&q);
sq=(int)ceil(sqrt((double)n));
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++) b[i]=a[i];
for(int i=;i<=n;i++) pos[i]=(i-)/sq+;
for(int i=;i<n;i++) if(pos[i]!=pos[i+]) rt[pos[i]]=i,ft[pos[i+]]=i+;
ft[]=;rt[pos[n]]=n;
for(int i=;i<=pos[n];i++) add[i]=;
for(int i=;i<=pos[n];i++) sort(b+ft[i],b+rt[i]+,cmp);
/*printf("sq = %d\n",sq);
for(int i=1;i<=n;i++) printf("%d ",pos[i]);printf("\n");
for(int i=1;i<=sq;i++) printf("%d ",ft[i]);printf("\n");
for(int i=1;i<=sq;i++) printf("%d ",rt[i]);printf("\n");*/
// while(1);
for(int i=;i<=q;i++)
{
char s[];
int x,y,c;
scanf("%s%d%d%d",s,&x,&y,&c);
if(s[]=='M')
{
change(x,y,c);
}
else
{
printf("%d\n",query(x,y,c));
}
}
return ;
}
2017-03-27 22:08:51