像优酷这样的网站需要怎么做,dw网页制作上机试题,赤峰浩诚网站建设有限公司,久霸高端网页版4170: 极光 Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 121 Solved: 64Description 若是万一琪露诺#xff08;俗称rhl#xff09;进行攻击#xff0c;什么都好#xff0c;冷静地回答她的问题来吸引她。对方表现出兴趣的话#xff0c;那就慢慢地反问。在她考… 4170: 极光 Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 121 Solved: 64 Description 若是万一琪露诺俗称rhl进行攻击什么都好冷静地回答她的问题来吸引她。对方表现出兴趣的话那就慢 慢地反问。在她考虑答案的时候趁机逃吧。就算是很简单的问题她一定也答不上来。 --《上古之魔书》 天空中出现了许多的北极光这些北极光组成了一个长度为n的正整数数列a[i],远古之魔书上记载到2个位置的g raze值为两者位置差与数值差的和 graze(x,y)|x-y||a[x]-a[y]|。 要想破解天罚就必须支持2种操作k都是正整数 Modify x k将第x个数的值修改为k。 Query x k询问有几个i满足graze(x,i)k。 由于从前的天罚被圣王lmc破解了所以rhl改进了她的法术询问不仅要考虑当前数列还要考虑任意历史版本 即统计任意位置上出现过的任意数值与当前的a[x]的graze值k的对数。某位置多次修改为同样的数值按多次 统计 Input 第1行两个整数n,q。分别表示数列长度和操作数。 第2行n个正整数代表初始数列。 第3~q2行每行一个操作。 N40000, 修改操作数40000, 询问操作数10000, Max{a[i]}(含修改)80000 Output 对于每次询问操作输出一个非负整数表示答案 Sample Input 3 5 2 4 3 Query 2 2 Modify 1 3 Query 2 2 Modify 1 2 Query 1 1 Sample Output 2 3 3 HINT Source 【分析】 那个公式是曼哈顿距离的形式把编号看成x数值看成y那就是在二维平面上不断给你一些点然后问你距离某个点曼哈顿距离小于等于k的有多少个。 曼哈顿距离画出来是一个菱形区域把它旋转即x,y)-(x-y,xy)就是一个矩形区域根据容斥分成4段求前缀。 那么加一个时间维就是一个经典的CDQ模型啦三维偏序嘛~ 1 #includecstdio2 #includecstdlib3 #includecstring4 #includeiostream5 #includealgorithm6 using namespace std;7 #define Maxn 400108 #define Maxm 500109
10 struct node {int a,b,c,id,f,ans;}t[Maxn*10];
11 int len0;
12 int ans[Maxm*10],w[Maxn*10];
13 char s[10];
14 int n,q;
15
16 void add(int a,int b,int c,int id,int f)
17 {
18 // printf(%d %d %d %d %d\n,a,b,c,id,f);
19 t[len].aa;t[len].bb;t[len].cc;t[len].idid;t[len].ff;
20 t[len].ans0;
21 }
22
23 bool cmp(node x,node y)
24 {
25 if(x.a!y.a) return x.ay.a;
26 return (x.by.b)?(x.cy.c):(x.by.b);
27 }
28 bool cmp2(int x,int y) {return (t[x].bt[y].b)?(t[x].ct[y].c):(t[x].bt[y].b);}
29
30 int cc[Maxm*10],nw[Maxm*10];
31 void ad(int x,int y) {for(int ix;iq1;ii(-i)) cc[i]y;}
32 int query(int x) {int as0;for(int ix;i1;i-i(-i)) ascc[i];return as;}
33
34 void ffind(int l,int r)
35 {
36 if(lr) return;
37 int mid(lr)1;
38 nw[0]0;for(int il;ir;i) nw[nw[0]]i;
39 sort(nw1,nw1nw[0],cmp2);
40 for(int i1;inw[0];i)
41 {
42 if(nw[i]midt[nw[i]].id0)
43 {
44 ad(t[nw[i]].c,1);
45 }
46 else if(nw[i]midt[nw[i]].id!0)
47 {
48 t[nw[i]].ansquery(t[nw[i]].c);
49 }
50 }
51 for(int il;ir;i) if(imidt[i].id0) ad(t[i].c,-1);
52 ffind(l,mid);ffind(mid1,r);
53 }
54
55 int main()
56 {
57 scanf(%d%d,n,q);
58 memset(ans,0,sizeof(ans));
59 for(int i1;in;i)
60 {
61 int x;scanf(%d,x);
62 w[i]x;
63 add(i-x,ix,1,0,0);
64 }ans[0]0;
65 for(int i1;iq;i)
66 {
67 int x,y;
68 scanf(%s%d%d,s,x,y);
69 if(s[0]Q)
70 {
71 add(x-w[x]y,xw[x]y,i1,ans[0],1);
72 add(x-w[x]-y-1,xw[x]-y-1,i1,ans[0],1);
73 add(x-w[x]-y-1,xw[x]y,i1,ans[0],-1);
74 add(x-w[x]y,xw[x]-y-1,i1,ans[0],-1);
75 }
76 else
77 {
78 add(x-y,xy,i1,0,0);
79 w[x]y;
80 }
81 }
82 sort(t1,t1len,cmp);
83 ffind(1,len);
84 for(int i1;ians[0];i) ans[i]0;
85 for(int i1;ilen;i) if(t[i].id!0) ans[t[i].id]t[i].f*t[i].ans;
86 // for(int i1;ilen;i) printf(%d %d %d %d %d %d\n,t[i].a,t[i].b,t[i].c,t[i].id,t[i].f,t[i].ans);
87 for(int i1;ians[0];i) printf(%d\n,ans[i]);
88 return 0;
89 } View Code 认真地开了数组大小很久还是RE干脆全部乘10了。。。 2017-03-26 16:40:39 转载于:https://www.cnblogs.com/Konjakmoyu/p/6623209.html
