C. Monsters And Spells

Monocarp is playing a computer game once again. He is a wizard apprentice, who only knows a single spell. Luckily, this spell can damage the monsters.

The level he's currently on contains nn monsters. The ii-th of them appears kiki seconds after the start of the level and has hihi health points. As an additional constraint, hi≤kihi≤ki for all 1≤i≤n1≤i≤n. All kiki are different.

Monocarp can cast the spell at moments which are positive integer amounts of second after the start of the level: 1,2,3,…1,2,3,… The damage of the spell is calculated as follows. If he didn't cast the spell at the previous second, the damage is 11. Otherwise, let the damage at the previous second be xx. Then he can choose the damage to be either x+1x+1 or 11. A spell uses mana: casting a spell with damage xx uses xx mana. Mana doesn't regenerate.

To kill the ii-th monster, Monocarp has to cast a spell with damage at least hihi at the exact moment the monster appears, which is kiki.

Note that Monocarp can cast the spell even when there is no monster at the current second.

The mana amount required to cast the spells is the sum of mana usages for all cast spells. Calculate the least amount of mana required for Monocarp to kill all monsters.

题意：有n个怪兽我们要消灭，第i个怪兽在第ki秒出现，生命值为hi，我们要在第ki秒消灭他

在第i秒的时候我们可以选择我们的攻击力：

1.当i-1秒没有攻击时第i秒攻击力只能是1

2.当i-1秒的攻击时x的时候我们可以选择第i秒的攻击力是x+1或者1

当ki秒出现血量为hi的怪物时，我们的攻击力必须到hi来打败他

思路：如果第r=ki秒要达到hi的话那么我们在第l=ki-hi+1秒的时候开始攻击

那么这一段的攻击就是len*(len+1)/2  (len是时间段

当然也有一段和一段重合的情况，那么我们的l就取最早开始的时间，r就取最晚结束的时间

这样就可以覆盖一整个重合的区间，

我们先把每个区间算出来按左端点排序，然后看下一个区间是不是和他重合

如果重合，那么我们的l就取最早开始的时间，r就取最晚结束的时间

如果不重合，我们就加上我0们已经得到的区间需要的攻击力

然后l和r取新的区间的l r 就可以了

/*
 .----------------.  .----------------.  .----------------.  .----------------. 
| .--------------. || .--------------. || .--------------. || .--------------. |
| |  ________    | || |  _________   | || | ____    ____ | || |     ____     | |
| | |_   ___ `.  | || | |_   ___  |  | || ||_   \  /   _|| || |   .'    `.   | |
| |   | |   `. \ | || |   | |_  \_|  | || |  |   \/   |  | || |  /  .--.  \  | |
| |   | |    | | | || |   |  _|  _   | || |  | |\  /| |  | || |  | |    | |  | |
| |  _| |___.' / | || |  _| |___/ |  | || | _| |_\/_| |_ | || |  \  `--'  /  | |
| | |________.'  | || | |_________|  | || ||_____||_____|| || |   `.____.'   | |
| |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
#define lowbit(x) x&(-x)
#define PI 3.1415926535
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int gcd(int a,int b){
	return b>0 ? gcd(b,a%b):a;
}
/*
int dx[8]={-2,-2,-1,1,2,2,-1,1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int dx[8]={-1,1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
*/
const int N=100+10;
int n;
int k[N],h[N];
struct name{
	int l,r;
}q[N];
bool cmp(name a,name b){
	return a.l 
}
void init(){
	int con=0;
	for(int i=1;i<=15;i++)con+=i;
}
void sjdhfb(){
	int djbhff=0;
	/*
	while
	*/
	for(int dd=1;dd<=4;dd++){
		djbhff+=dd;
	}
}
void sove(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>k[i];
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=1;i<=n;i++){
		q[i].l =k[i]-h[i]+1;
		q[i].r =k[i];
	}
	sort(q+1,q+1+n,cmp);
	int s=q[1].l ,e=q[1].r ;
	int con=0;
	for(int i=2;i<=n;i++){
		if(q[i].l <=e){
			s=min(q[i].l ,s);
			e=max(q[i].r ,e);
		}else{
			int len=e-s+1;
			con+=len*(len+1)/2;
			s=q[i].l ;
			e=q[i].r ;
		}
	}
	int len=e-s+1;
	con+=len*(len+1)/2;
	cout<
}
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	int t=1;
	cin>>t;
	init();
	sjdhfb();
	init();
	while(t--){
		sove();
	}
	return 0;
}