问题1429--三角形

1429: 三角形

时间限制: 2 Sec  内存限制: 128 MB
提交: 344  解决: 23
[状态] [讨论版] [提交] [命题人:]
题目描述

给定n条边,把这n1<=n<=100000)条从1标号到n

现在有m1<=m<=100000)个操作,每个操作分为两类:

A类操作改变第i条边的值为j

B类操作给定第i条边和第j条边,问在剩下的边中,有多少条边可以和边iji不等于j)组成三角形。

输入

第一行为一个整数T1<=T<=5)表示测试数据的组数。

每组测试数据:

1一个整数n,表示有n条边。

2n个由空格隔开的整数,第i个整数表示第i条边的长度ai1<=ai<=500000)。

3一个整数m,表示有m个操作。

接下有m行个操作,每行包含3个由空格隔开的整数kij

如果是A类操作,k1,表示改变第i条边的值为j

如果是B类操作,k2,问在剩下的边中,有多少条边可以和边ij组成三角形。

输出

对于每一个B类操作输出一个整数到一行。

样例输入 Copy
2
5
1 2 3 4 5
3
2 1 2
1 5 3
2 4 5
10
5 5 20 100 20 13 17 28 200 98
3
1 1 81
2 4 5
2 9 10
样例输出 Copy
0
2
2
0
来源/分类